剑指Offer:重建二叉树

@ [TOC]

重建二叉树

题意

• 根据给定的树的前序遍历和中序遍历，重建该二叉树

思路

• 首先根节点非常好确定，一定是pre[0]
• 然后我们需要在in中，找到根节点的位置，该位置就把整颗树的左右子树分开了，可以分别获取到左右子树的总共的树节点数量
• 现在根节点确定了，接下来需要确定根节点的左右孩子节点
• 根节点的左孩子节点，一定是整颗树根节点的左子树的根节点
• 根节点的右孩子节点，一定是整颗树根节点的右子树的根节点
• 那么接下来本质上就是在不同的区间之内寻找根节点，那么和上述的过程是一致的

代码

    class Solution {
        
        public TreeNode reConstructBinaryTree(int [] pre,int [] in) {
            TreeNode root=reBuildTree(pre,0,pre.length-1,in,0,in.length-1);
            return root;
        }

        private TreeNode reBuildTree(int[] pre, int preStart, int preEnd, int[] in, int inStart, int inEnd) {

            if (preStart > preEnd || inStart > inEnd){
                return null;
            }
            TreeNode root = new TreeNode(pre[preStart]);
            for (int i = inStart; i <= inEnd; i++) {

                if (in[i] == pre[preStart]){
                    root.left = reBuildTree(pre, preStart +1, preStart + i - inStart, in, inStart, i-1);
                    root.right = reBuildTree(pre, i - inStart + preStart + 1, preEnd, in, i+1, inEnd);
                    break;
                }
            }

            return root;
        }
    }