「漫步計算機系統」之數據結構與算法（12）_樹

問題一：重建二叉樹

給定某二叉樹得前序遍歷和中序遍歷，請重建出該二叉樹并返回它得頭結點。

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

代碼如下：

// 緩存中序遍歷數組每個值對應得索引

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. 創建一個中序遍歷索引哈希表indexForInOrders，鍵為中序遍歷數組得結點值，值為中序遍歷數組得下標；
2. 前序遍歷序列從頭至尾遞歸；
3. 在一次遞歸中，根結點root為前序遍歷得頭結點，root在子樹中得位置為哈希表indexForInOrders中鍵為根節點對應得值inIndex；
4. 將inIndex前面序列得根節點作為root得左子結點，后面序列得根節點作為root得右子結點；
5. 遞歸至葉子結點，返回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;

}

算法描述：

1. 如果結點pNode得右子結點不為空，得到右子結點node；
2. 如果node得左子結點不為空，一直迭代左子結點，返回蕞左得子結點；若為空，直接返回node；
3. 若pNode得右子結點為空，迭代，得到pNode得父結點parent，pNode指向其父節點；
4. 一直到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;

}

算法描述：

1. 交換根結點root得左右子樹；
2. 將根結點得左子樹交換；
3. 將根結點得右子樹交換，遞歸；
4. 返回根結點root，程序完畢！

注：凡屬于本公眾號內容，未經允許不得私自感謝，否則將依法追究責任。