[Leetcode] Construct Binary Tree from Traversal 根据

caoym 发布于2019-08-14 12:32 / 496人阅读

摘要：二分法复杂度时间空间思路我们先考察先序遍历序列和中序遍历序列的特点。对于中序遍历序列，根在中间部分，从根的地方分割，前半部分是根的左子树，后半部分是根的右子树。

Construct Binary Tree from Preorder and Inorder Traversal

Given preorder and inorder traversal of a tree, construct the binary tree.

二分法 复杂度

时间 O(N^2) 空间 O(N)

思路

我们先考察先序遍历序列和中序遍历序列的特点。对于先序遍历序列，根在最前面，后面部分存在一个分割点，前半部分是根的左子树，后半部分是根的右子树。对于中序遍历序列，根在中间部分，从根的地方分割，前半部分是根的左子树，后半部分是根的右子树。当我们从上向下构建树时，我们可以通过先序遍历序列知道根节点的值，但是如何知道两个序列是在哪里分割的呢？这就要依靠中序序列了。我们在中序序列中找到这个根的值，根据这个根的坐标，我们可以知道这个根左子树有多少个节点，右子树有多少个节点。然后我们根据这个将先序遍历序列分割，通过递归再次取每个部分的第一个作为根，同时为了下一次能准确的计算出左右子树各有多少节点，我们也要同时对中序遍历序列进行分割。

代码

public class Solution {
    
    int preStart = 0;
    
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        if(preorder.length == 0 || inorder.length == 0) return null;
        return helper(0,inorder.length - 1,preorder,inorder);
    }
    
    private TreeNode helper(int inStart, int inEnd, int[] preorder, int[] inorder){
        // Base情况
        if(preStart > preorder.length || inStart > inEnd){
            return null;
        }
        TreeNode root = new TreeNode(preorder[preStart]);
        int inMid = 0;
        // 找到根在中序序列中的位置，从而知道先序中的分割点
        for(int i = inStart ; i <= inEnd; i++){
            if(inorder[i] == preorder[preStart]){
                inMid = i;
            }
        }
        preStart++;
        // 例如先序序列 1(234)(567) 中2是左子树的根
        root.left = helper(inStart, inMid - 1, preorder, inorder);
        // 先序序列 1(234)(567) 中5是右子树的根
        root.right = helper(inMid + 1, inEnd, preorder, inorder);
        return root;
    }
}

Construct Binary Tree from Inorder and Postorder Traversal

Given inorder and postorder traversal of a tree, construct the binary tree.

Note: You may assume that duplicates do not exist in the tree.

二分法 复杂度

时间 O(N^2) 空间 O(N)

思路

中序序列仍然是以根节点划分为左右两边，而后序序列的特点则是根在最后，然后在跟前面的那部分中，前面部分是左子树，后面的部分是右子树。所以其实我们就是把上一题给反过来了。这题我们将后序序列的指针全局化，这样我们可以先建好右子树，再建左子树，而指针只要顺序从后向前就行了。

代码

public class Solution {
    
    int postEnd = 0;
    
    public TreeNode buildTree(int[] inorder, int[] postorder) {
        postEnd = postorder.length - 1;
        return helper(postorder, inorder, 0, inorder.length - 1);
    }
    
    private TreeNode helper(int[] postorder, int[] inorder, int inStart, int inEnd){
        if(postEnd < 0 || inStart > inEnd){
            return null;
        }
        TreeNode root = new TreeNode(postorder[postEnd--]);
        int inMid = 0;
        // 找到中序序列的根节点
        for(int i = inStart; i <= inEnd; i++){
            if(inorder[i] == root.val){
                inMid = i;
                break;
            }
        }
        // 建好右子树
        root.right = helper(postorder, inorder, inMid + 1, inEnd);
        // 建好左子树
        root.left = helper(postorder, inorder, inStart, inMid - 1);
        return root;
    }
}

云服务器 GPU云服务器 binary-tree binary-search-tree Traversal Construct

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/64544.html

[LintCode/LeetCode] Construct Binary Tree from Tr

摘要：做了几道二分法的题目练手，发现这道题已经淡忘了，记录一下。这道题目的要点在于找的区间。边界条件需要注意若或数组为空，返回空当前进到超出末位，或超过，返回空每次创建完根节点之后，要将加，才能进行递归。 Construct Binary Tree from Inorder and Preorder Traversal Problem Given preorder and inorder t...

马忠志 2019-08-14 15:40 评论0 收藏0
前端 | 每天一个 LeetCode

摘要：在线网站地址我的微信公众号完整题目列表从年月日起，每天更新一题，顺序从易到难，目前已更新个题。这是项目地址欢迎一起交流学习。这篇文章记录我练习的 LeetCode 题目，语言 JavaScript。在线网站：https://cattle.w3fun.com GitHub 地址：https://github.com/swpuLeo/ca...我的微信公众号： showImg(htt...

张汉庆 2019-08-23 13:42 评论0 收藏0
Construct Binary Tree from Traversal

摘要：思路在的顺序里，先，然后再左右。所以根据可以知道的。接着再分别在和的里面重复找以及左右的过程。首先的包括和，以及对应的起始和结束位置，对应的起始和结束位置。返回值为，因为每个里要一个，同时找到它的和，左右节点通过返回值获得。同时的不需要了。 From Preorder and Inorder 思路在preorder的顺序里，先root，然后再左右。所以根据preorder可以知道roo...

wenshi11019 2019-08-14 17:11 评论0 收藏0
[Leetcode] Binary Tree Traversal 二叉树遍历

摘要：栈迭代复杂度时间空间递归栈空间对于二叉树思路用迭代法做深度优先搜索的技巧就是使用一个显式声明的存储遍历到节点，替代递归中的进程栈，实际上空间复杂度还是一样的。对于先序遍历，我们出栈顶节点，记录它的值，然后将它的左右子节点入栈，以此类推。 Binary Tree Preorder Traversal Given a binary tree, return the preorder tr...

RaoMeng 2019-08-14 12:25 评论0 收藏0
LeetCode 精选TOP面试题【51 ~ 100】

摘要：有效三角形的个数双指针最暴力的方法应该是三重循环枚举三个数字。总结本题和三数之和很像，都是三个数加和为某一个值。所以我们可以使用归并排序来解决这个问题。注意因为归并排序需要递归，所以空间复杂度为 ...

Clect 2021-11-15 11:38 评论0 收藏0