重建二叉树

末蓝、 2021-11-16 15:14 264阅读 0赞

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

package com.zgw.newcoder;
    
    /**
     * Created by Zhaogw&Lss on 2019/7/27.
     */
    class TreeNode{
        TreeNode left;
        TreeNode right;
        int value;
    
        public TreeNode(int value) {
            this.value = value;
        }
    
        @Override
        public String toString() {
            return "TreeNode{" +
                    "left=" + left +
                    ", right=" + right +
                    ", value=" + value +
                    '}';
        }
    }
    public class Solution5 {
        public static void main(String[] args) {
            int preorder[] = {1, 2, 4, 7, 3, 5, 6, 8};
            int inorder[] = {4, 7, 2, 1, 5, 3, 8, 6};
            Solution5 solution5 = new Solution5();
            TreeNode trees = solution5.reConstructBinaryTree(preorder,inorder);
            System.out.println(trees);
        }
        public TreeNode reConstructBinaryTree(int[] pre,int[] in){
            return reConstructBinaryTree(pre,0,pre.length-1,in,0,in.length-1);
        }
    
        private TreeNode reConstructBinaryTree(int[] pre, int startPre, int endPre, int[] in, int startIn, int endIn) {
            if (startPre>endPre||startIn>endIn){
                return null;
            }
            /**
             * 
             递归思想，每次将左右两颗子树当成新的子树进行处理，中序的左右子树索引很好找，
             前序的开始结束索引通过计算中序中左右子树的大小来计算，然后递归求解，
             直到startPre>endPre||startIn>endIn说明子树整理完到。方法每次返回左子树活右子树的根节点
             */
            TreeNode root=new TreeNode(pre[startPre]);
            for (int i = startIn; i <= endIn ; i++) {
                if (pre[startPre] == in[i]){
                root.left = reConstructBinaryTree(pre,startPre+1,startPre+i-startIn,in,startIn,i-1);
                root.right = reConstructBinaryTree(pre,i-startIn+startPre+1,endPre,in,i+1,endIn);
    
                }
    
            }
            return root;
        }
    
    }

参考:https://blog.csdn.net/roycon/article/details/79772639