每天一道leetcode-105从前序和中序序列构建二叉树

乔戈里

发布于 2019-09-17 16:03:43

3600

发布于 2019-09-17 16:03:43

文章被收录于专栏：Java那些事Java那些事

前言

今天的题目 每天的题目见github(看最新的日期): https://github.com/gzc426

昨天的题解

每天一道leetcode-105从前序和中序序列构建二叉树

题目

根据一棵树的前序遍历与中序遍历构造二叉树。

注意: 你可以假设树中没有重复的元素。

例如，给出

前序遍历 preorder = [3,9,20,15,7] 中序遍历 inorder = [9,3,15,20,7] 返回如下的二叉树：

题目详解

思路

我们首先要得到从前序序列中获取根节点，然后遍历中序序列，找到根节点的位置，以此直到其左子树和右子树的范围。当我得到其左子树之后，事情就开始重复了，我们仍然需要根据前序序列中找到这颗左子树的根节点，然后再根据中序序列得到这颗左子树根节点的左右子树,就这样一直重复这个过程，直到，左子树只有一个节点，那么也就是在递归的最深的那一层，这时候就把这个节点返回，然后就一层层回溯，这样就完成了左子树的构建
对于右子树也是同理。

代码

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    //写法仿照 剑指offer 面试题7 重建二叉树

    public TreeNode buildTree(int[] preorder, int[] inorder) {
        if(preorder == null || inorder == null || preorder.length==0){
            return null;
        }
        return buildCore(preorder,0,preorder.length-1,inorder,0,inorder.length-1);
    }
    private TreeNode buildCore(int[] preorder,int preSt,int preEnd,int[] inorder,int inSt,int inEnd){
        //前序遍历第一个节点是根节点
        int rootValue = preorder[preSt];
        TreeNode root = new TreeNode(rootValue);

        //前序序列只有根节点
        if(preSt == preEnd){
            return root;
        }
        //遍历中序序列，找到根节点的位置
        int rootInorder = inSt;
        while(inorder[rootInorder]!=rootValue&&rootInorder<=inEnd){
            rootInorder++;
        }

        //左子树的长度
        int leftLength = rootInorder - inSt;
        //前序序列中左子树的最后一个节点
        int leftPreEnd = preSt + leftLength;

        //左子树非空 左子树长度大于等于0
        if(leftLength>0){
            //重建左子树
            root.left = buildCore(preorder,preSt+1,leftPreEnd,inorder,inSt,inEnd);
        }
        //右子树非空 preEnd 和prest是前序数组的结尾和开头，相减就是长度，如果左子树长度小于整个长度
        //那么说明右子树肯定 存在。那么对右子树也进行同样的构建树的操作。
        if(leftLength < preEnd - preSt){
            //重建右子树
            root.right = buildCore(preorder,leftPreEnd +1,preEnd,inorder,rootInorder+1,inEnd);
        }
        return root;
    }
}