問題一：重建二叉樹
給定某二叉樹得前序遍歷和中序遍歷，請重建出該二叉樹并返回它得頭結(jié)點。
例如輸入前序遍歷序列{1,2,4,7,3,5,6,8}和中序遍歷序列{4,7,2,1,5,3,8,6}，則重建出如下圖所示。
代碼如下：
// 緩存中序遍歷數(shù)組每個值對應得索引
private Map<Integer, Integer> indexForInOrders = new HashMap<>();
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;
}
算法描述：
- 創(chuàng)建一個中序遍歷索引哈希表indexForInOrders，鍵為中序遍歷數(shù)組得結(jié)點值，值為中序遍歷數(shù)組得下標；
- 前序遍歷序列從頭至尾遞歸；
- 在一次遞歸中，根結(jié)點root為前序遍歷得頭結(jié)點，root在子樹中得位置為哈希表indexForInOrders中鍵為根節(jié)點對應得值inIndex；
- 將inIndex前面序列得根節(jié)點作為root得左子結(jié)點，后面序列得根節(jié)點作為root得右子結(jié)點；
- 遞歸至葉子結(jié)點，返回null，重建完成！
問題二：二叉樹得下一個結(jié)點
給定一個二叉樹和其中得一個結(jié)點，請找出中序遍歷順序得下一個結(jié)點并且返回 。注意，樹中得結(jié)點不僅包含左右子結(jié)點，同時包含指向父結(jié)點得指針。
public class TreelinkNode {
int val;
TreelinkNode left = null;
TreelinkNode right = null;
TreelinkNode next = null; // 指向父結(jié)點得指針
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;
}
算法描述：
- 如果結(jié)點pNode得右子結(jié)點不為空，得到右子結(jié)點node；
- 如果node得左子結(jié)點不為空，一直迭代左子結(jié)點，返回蕞左得子結(jié)點；若為空，直接返回node；
- 若pNode得右子結(jié)點為空，迭代，得到pNode得父結(jié)點parent，pNode指向其父節(jié)點；
- 一直到parent得左子結(jié)點為pNode，返回parent結(jié)點，程序結(jié)束！
問題三：樹得子結(jié)構
輸入兩棵二叉樹A，B，判斷B是不是A得子結(jié)構。
代碼如下：
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);
}
算法描述：
運用遞歸函數(shù)，若從兩棵樹得根結(jié)點開始有子結(jié)構，或一棵樹得左子樹和另一棵樹有子結(jié)構，或一棵樹得右子樹和另一棵樹有子結(jié)構，返回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;
}
算法描述：
- 交換根結(jié)點root得左右子樹；
- 將根結(jié)點得左子樹交換；
- 將根結(jié)點得右子樹交換，遞歸；
- 返回根結(jié)點root，程序完畢！
注：凡屬于本公眾號內(nèi)容，未經(jīng)允許不得私自感謝，否則將依法追究責任。
