[LintCode/LeetCode] Construct Binary Tree from Tr

馬忠志發布于2019-08-14 15:40 / 1438人閱讀

摘要：做了幾道二分法的題目練手，發現這道題已經淡忘了，記錄一下。這道題目的要點在于找的區間。邊界條件需要注意若或數組為空，返回空當前進到超出末位，或超過，返回空每次創建完根節點之后，要將加，才能進行遞歸。

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

文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。

轉載請注明本文地址：http://specialneedsforspecialkids.com/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