[LintCode/LeetCode] Construct Binary Tree from Tr

马忠志发布于2019-08-14 15:40 / 1440人阅读

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

Construct Binary Tree from Inorder and Preorder Traversal Problem

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

Notice

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

Example

Given in-order [1,2,3] and pre-order [2,1,3], return a tree:

  2
 / 
1   3

Note

许久未更。做了几道二分法的题目练手，发现这道题已经淡忘了，记录一下。

这道题目的要点在于找inorder的区间。preStart每增加一次，就对应一个新的子树。每个子树的根节点都可以在inorder的中间某处找到，以此为界，左边是这个根节点的左子树，右边是右子树。不断递归，得解。

边界条件需要注意：

若preorder或inorder数组为空，返回空；

当preStart前进到超出preorder末位，或inStart超过inEnd，返回空；

每次创建完根节点之后，要将preStart加1，才能进行递归。

Solution

public class Solution {
    int preStart = 0;
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        if (preorder.length == 0 || inorder.length == 0) return null;
        return helper(preorder, inorder, 0, preorder.length-1);
    }
    public TreeNode helper(int[] preorder, int[] inorder, int inStart, int inEnd) {
        if (preStart >= preorder.length || inStart > inEnd) return null;
        int index = 0;
        for (int i = inStart; i <= inEnd; i++) {
            if (inorder[i] == preorder[preStart]) {
                index = i;
                break;
            }
        }
        TreeNode root = new TreeNode(preorder[preStart++]);
        root.left = helper(preorder, inorder, inStart, index-1);
        root.right = helper(preorder, inorder, index+1, inEnd);
        return root;
    }
}

Construct Binary Tree from Inorder and Postorder Traversal Problem

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

Notice

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

Example

Given inorder [1,2,3] and postorder [1,3,2], return a tree:

  2
 / 
1   3

Note

和先序+中序方法一样，不过这次是逆推，递归的时候先右子树，后左子树即可。

Solution Recursion

public class Solution {
    int postEnd;
    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;
    }
}

Using Stack

public class Solution {
    public TreeNode buildTree(int[] inorder, int[] postorder) {
        if (inorder == null || inorder.length < 1) return null;
        int i = inorder.length - 1;
        int p = i;
        TreeNode node;
        TreeNode root = new TreeNode(postorder[postorder.length - 1]);
        Stack stack = new Stack<>();
        stack.push(root);
        p--;
        while (true) {
            if (inorder[i] == stack.peek().val) { // inorder[i] is on top of stack, pop stack to get its parent to get to left side
                if (--i < 0) break;
                node = stack.pop();
                if (!stack.isEmpty() && inorder[i] == stack.peek().val) continue;
                node.left = new TreeNode(postorder[p]);
                stack.push(node.left);
            } else { // inorder[i] is not on top of stack, postorder[p] must be right child
                node = new TreeNode(postorder[p]);
                stack.peek().right = node;
                stack.push(node);
            }
            p--;
        }
        return root;
    }
}

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

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

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

[LintCode/LeetCode] Binary Tree Level Order Traver

Problem Given a binary tree, return the level order traversal of its nodes values. (ie, from left to right, level by level). For example:Given binary tree {3,9,20,#,#,15,7}, 3 / 9 20 / ...

makeFoxPlay 2019-08-14 15:48 评论0 收藏0
Construct Binary Tree from Preorder and Inorder Tr

摘要：解题思路利用递归思想，先序遍历的第一个元素就是根节点，然后在中序遍历中寻找该节点，该节点左边的就是左子树，右边的是右子树。 Construct Binary Tree from Preorder and Inorder TraversalGiven preorder and inorder traversal of a tree, construct the binary tree. ...

tuomao 2019-08-16 10:26 评论0 收藏0
[LintCode/LeetCode] Binary Tree Zigzag Level Orde

Problem Given a binary tree, return the zigzag level order traversal of its nodes values. (ie, from left to right, then right to left for the next level and alternate between). Example Given binary tr...

AlphaGooo 2019-08-14 15:40 评论0 收藏0
[LintCode/LeetCode] Binary Tree Serialization

摘要：这里要注意的是的用法。所以记住，用可以从自动分离出数组。跳过第一个元素并放入数组最快捷语句建立的用意记录处理过的结点并按处理所有结点和自己的连接下面先通过判断，再修改的符号的顺序，十分巧妙更轻便的解法 Problem Design an algorithm and write code to serialize and deserialize a binary tree. Writin...

keithyau 2019-08-14 15:12 评论0 收藏0
[LintCode/LeetCode] Balanced Binary Tree

摘要：根据二叉平衡树的定义，我们先写一个求二叉树最大深度的函数。在主函数中，利用比较左右子树的差值来判断当前结点的平衡性，如果不满足则返回。 Problem Given a binary tree, determine if it is height-balanced. For this problem, a height-balanced binary tree is defined as...

morgan 2019-08-14 15:33 评论0 收藏0