【漫步计算机系统】之数据结构与算法（11）：树Ⅰ
问题一：重建二叉树
给定某二叉树的前序遍历和中序遍历，请重建出该二叉树并返回它的头结点。
例如输入前序遍历序列{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;}
算法描述：
创建一个中序遍历索引哈希表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，程序完毕！