問題一：重建二叉樹
給定某二叉樹的前序遍歷和中序遍歷，請重建出該二叉樹並返回它的頭結點。
例如
輸入前序遍歷序列{1，2，4，7，3，5，6，8}和中序遍歷序列{4，7，2，1，5，3，8，6}，則重建出如下圖所示。
程式碼如下：
// 快取中序遍歷陣列每個值對應的索引
private Map
public TreeNode reConstructBinaryTree（int［］ pre， int［］ in） {
for （int i = 0； i < in。length； i++）
indexForInOrders。put（in［i］， i）；
return reConstructBinaryTree（pre， 0， pre。length - 1， 0）；
}
private TreeNode reConstructBinaryTree（int［］ pre， int preL， int preR， int inL） {
if （preL > preR）
return null；
TreeNode root = new TreeNode（pre［preL］）；
int inIndex = indexForInOrders。get（root。val）；
int leftTreeSize = inIndex - inL；
root。left = reConstructBinaryTree（pre， preL + 1， preL + leftTreeSize， inL）；
root。right = reConstructBinaryTree（pre， preL + leftTreeSize + 1， preR， inL + leftTreeSize + 1）；
return root；
}
演算法描述：
建立一箇中序遍歷索引雜湊表indexForInOrders，鍵為中序遍歷陣列的結點值，值為中序遍歷陣列的下標；
前序遍歷序列從頭至尾遞迴；
在一次遞迴中，根結點root為前序遍歷的頭結點，root在子樹中的位置為雜湊表indexForInOrders中鍵為根節點對應的值inIndex；
將inIndex前面序列的根節點作為root的左子結點，後面序列的根節點作為root的右子結點；
遞迴至葉子結點，返回null，重建完成！
問題二：二叉樹的下一個結點
給定一個二叉樹和其中的一個結點，請找出中序遍歷順序的下一個結點並且返回 。注意，樹中的結點不僅包含左右子結點，同時包含指向父結點的指標。
public class TreeLinkNode {
int val；
TreeLinkNode left = null；
TreeLinkNode right = null；
TreeLinkNode next = null； // 指向父結點的指標
TreeLinkNode（int val） {
this。val = val；
}
}
程式碼如下：
public TreeLinkNode GetNext（TreeLinkNode pNode） {
if （pNode。right ！= null） {
TreeLinkNode node = pNode。right；
while （node。left ！= null）
node = node。left；
return node；
} else {
while （pNode。next ！= null） {
TreeLinkNode parent = pNode。next；
if （parent。left == pNode）
return parent；
pNode = pNode。next；
}
}
return null；
}
演算法描述：
如果結點pNode的右子結點不為空，得到右子結點node；
如果node的左子結點不為空，一直迭代左子結點，返回最左的子結點；若為空，直接返回node；
若pNode的右子結點為空，迭代，得到pNode的父結點parent，pNode指向其父節點；
一直到parent的左子結點為pNode，返回parent結點，程式結束！
問題三：樹的子結構
輸入兩棵二叉樹A，B，判斷B是不是A的子結構。
程式碼如下：
public boolean HasSubtree（TreeNode root1， TreeNode root2） {
if （root1 == null || root2 == null）
return false；
return isSubtreeWithRoot（root1， root2） || HasSubtree（root1。left， root2） || HasSubtree（root1。right， root2）；
}
private boolean isSubtreeWithRoot（TreeNode root1， TreeNode root2） {
if （root2 == null）
return true；
if （root1 == null）
return false；
if （root1。val ！= root2。val）
return false；
return isSubtreeWithRoot（root1。left， root2。left） && isSubtreeWithRoot（root1。right， root2。right）；
}
演算法描述：
運用遞迴函式，若從兩棵樹的根結點開始有子結構，或一棵樹的左子樹和另一棵樹有子結構，或一棵樹的右子樹和另一棵樹有子結構，返回true；
問題四：二叉樹的映象
操作給定的二叉樹，將其變換為源二叉樹的映象。
程式碼如下：
public TreeNode Mirror（TreeNode root） {
if （root == null）
return root；
swap（root）；
Mirror（root。left）；
Mirror（root。right）；
return root；
}
private void swap（TreeNode root） {
TreeNode t = root。left；
root。left = root。right；
root。right = t；
}
演算法描述：
交換根結點root的左右子樹；
將根結點的左子樹交換；
將根結點的右子樹交換，遞迴；
返回根結點root，程式完畢！
注：凡屬於本公眾號內容，未經允許不得私自轉載，否則將依法追究侵權責任。
