問(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;
}
算法描述:
- 創(chuàng)建一個(gè)中序遍歷索引哈希表indexForInOrders,鍵為中序遍歷數(shù)組得結(jié)點(diǎn)值,值為中序遍歷數(shù)組得下標(biāo);
- 前序遍歷序列從頭至尾遞歸;
- 在一次遞歸中,根結(jié)點(diǎn)root為前序遍歷得頭結(jié)點(diǎn),root在子樹(shù)中得位置為哈希表indexForInOrders中鍵為根節(jié)點(diǎn)對(duì)應(yīng)得值inIndex;
- 將inIndex前面序列得根節(jié)點(diǎn)作為root得左子結(jié)點(diǎn),后面序列得根節(jié)點(diǎn)作為root得右子結(jié)點(diǎn);
- 遞歸至葉子結(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;
}
算法描述:
- 如果結(jié)點(diǎn)pNode得右子結(jié)點(diǎn)不為空,得到右子結(jié)點(diǎn)node;
- 如果node得左子結(jié)點(diǎn)不為空,一直迭代左子結(jié)點(diǎn),返回蕞左得子結(jié)點(diǎn);若為空,直接返回node;
- 若pNode得右子結(jié)點(diǎn)為空,迭代,得到pNode得父結(jié)點(diǎn)parent,pNode指向其父節(jié)點(diǎn);
- 一直到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;
}
算法描述:
- 交換根結(jié)點(diǎn)root得左右子樹(shù);
- 將根結(jié)點(diǎn)得左子樹(shù)交換;
- 將根結(jié)點(diǎn)得右子樹(shù)交換,遞歸;
- 返回根結(jié)點(diǎn)root,程序完畢!
注:凡屬于本公眾號(hào)內(nèi)容,未經(jīng)允許不得私自感謝,否則將依法追究感謝對(duì)創(chuàng)作者的支持責(zé)任。