【剑指offer】重建二叉树

朱雀 2022-06-16 12:17 194阅读 0赞

## 题目描述 ##

输入某二叉树的前序遍历和中序遍历的结果，请重建出该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。例如输入前序遍历序列\{1,2,4,7,3,5,6,8\}和中序遍历序列\{4,7,2,1,5,3,8,6\}，则重建二叉树并返回。

--------------------

public class TestReConstructBinaryTree {
        public TreeNode reConstructBinaryTree(int[] pre, int[] in) {
            TreeNode root = reConstructBinaryTree(pre, 0, pre.length - 1, in, 0, in.length - 1);
            return root;
        }
    
        // 前序遍历{1,2,4,7,3,5,6,8} 中序遍历序列{4,7,2,1,5,3,8,6}
        public TreeNode reConstructBinaryTree(int[] pre, int preStart, int preEnd, int[] in, int inStart, int inEnd) {
            if (preStart > preEnd || inStart > inEnd) {
                return null;
            }
            TreeNode root = new TestReConstructBinaryTree().new TreeNode(pre[preStart]);// 根节点
            for (int i = inStart; i <= inEnd; i++) {
       // 遍历中序列
                if (in[i] == pre[preStart]) {
                    int leftLength = i - inStart;// 左子树长度
                    root.left = reConstructBinaryTree(pre, preStart + 1, preStart + leftLength, in, inStart, i - 1);
                    root.right = reConstructBinaryTree(pre, preStart + leftLength + 1, preEnd, in, i + 1, inEnd);
                }
            }
            return root;
        }
    
        // 递归前序遍历
        public void preOrder(TreeNode t) {
            if (t != null) {
                System.out.print(t.val);
                preOrder(t.left);
                preOrder(t.right);
            }
        }
    
        //树节点定义
        class TreeNode {
            int val;
            TreeNode left;
            TreeNode right;
    
            TreeNode() {
    
            }
    
            TreeNode(int x) {
                val = x;
            }
        }
    
    
        public static void main(String[] args) {
            int[] pre = {
       1,2,4,7,3,5,6,8};
            int[] in = {
       4,7,2,1,5,3,8,6};
            TreeNode t = new TestReConstructBinaryTree().reConstructBinaryTree(pre, in);
            new TestReConstructBinaryTree().preOrder(t) ;
        }
    }