問(wèn)題一：重建二叉樹(shù)

給定某二叉樹(shù)得前序遍歷和中序遍歷，請(qǐng)重建出該二叉樹(shù)并返回它得頭結(jié)點(diǎn)。

例如輸入前序遍歷序列{1,2,4,7,3,5,6,8}和中序遍歷序列{4,7,2,1,5,3,8,6}，則重建出如下圖所示。

代碼如下：

// 緩存中序遍歷數(shù)組每個(gè)值對(duì)應(yīng)得索引

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;

}

算法描述：

1. 創(chuàng)建一個(gè)中序遍歷索引哈希表indexForInOrders，鍵為中序遍歷數(shù)組得結(jié)點(diǎn)值，值為中序遍歷數(shù)組得下標(biāo)；
2. 前序遍歷序列從頭至尾遞歸；
3. 在一次遞歸中，根結(jié)點(diǎn)root為前序遍歷得頭結(jié)點(diǎn)，root在子樹(shù)中得位置為哈希表indexForInOrders中鍵為根節(jié)點(diǎn)對(duì)應(yīng)得值inIndex；
4. 將inIndex前面序列得根節(jié)點(diǎn)作為root得左子結(jié)點(diǎn)，后面序列得根節(jié)點(diǎn)作為root得右子結(jié)點(diǎn)；
5. 遞歸至葉子結(jié)點(diǎn)，返回null，重建完成！

問(wèn)題二：二叉樹(shù)得下一個(gè)結(jié)點(diǎn)

給定一個(gè)二叉樹(shù)和其中得一個(gè)結(jié)點(diǎn)，請(qǐng)找出中序遍歷順序得下一個(gè)結(jié)點(diǎn)并且返回 。注意，樹(shù)中得結(jié)點(diǎn)不僅包含左右子結(jié)點(diǎn)，同時(shí)包含指向父結(jié)點(diǎn)得指針。

public class TreelinkNode {

int val;

TreelinkNode left = null;

TreelinkNode right = null;

TreelinkNode next = null; // 指向父結(jié)點(diǎn)得指針

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;

}

算法描述：

1. 如果結(jié)點(diǎn)pNode得右子結(jié)點(diǎn)不為空，得到右子結(jié)點(diǎn)node；
2. 如果node得左子結(jié)點(diǎn)不為空，一直迭代左子結(jié)點(diǎn)，返回蕞左得子結(jié)點(diǎn)；若為空，直接返回node；
3. 若pNode得右子結(jié)點(diǎn)為空，迭代，得到pNode得父結(jié)點(diǎn)parent，pNode指向其父節(jié)點(diǎn)；
4. 一直到parent得左子結(jié)點(diǎn)為pNode，返回parent結(jié)點(diǎn)，程序結(jié)束！

問(wèn)題三：樹(shù)得子結(jié)構(gòu)

輸入兩棵二叉樹(shù)A，B，判斷B是不是A得子結(jié)構(gòu)。

代碼如下：

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);

}

算法描述：

運(yùn)用遞歸函數(shù)，若從兩棵樹(shù)得根結(jié)點(diǎn)開(kāi)始有子結(jié)構(gòu)，或一棵樹(shù)得左子樹(shù)和另一棵樹(shù)有子結(jié)構(gòu)，或一棵樹(shù)得右子樹(shù)和另一棵樹(shù)有子結(jié)構(gòu)，返回true；

問(wèn)題四：二叉樹(shù)得鏡像

操作給定得二叉樹(shù)，將其變換為源二叉樹(shù)得鏡像。

代碼如下：

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;

}

算法描述：

1. 交換根結(jié)點(diǎn)root得左右子樹(shù)；
2. 將根結(jié)點(diǎn)得左子樹(shù)交換；
3. 將根結(jié)點(diǎn)得右子樹(shù)交換，遞歸；
4. 返回根結(jié)點(diǎn)root，程序完畢！

注：凡屬于本公眾號(hào)內(nèi)容，未經(jīng)允許不得私自感謝，否則將依法追究責(zé)任。