成人国产在线小视频_日韩寡妇人妻调教在线播放_色成人www永久在线观看_2018国产精品久久_亚洲欧美高清在线30p_亚洲少妇综合一区_黄色在线播放国产_亚洲另类技巧小说校园_国产主播xx日韩_a级毛片在线免费

資訊專欄INFORMATION COLUMN

[LintCode/LeetCode] Construct Binary Tree from Tr

馬忠志 / 1453人閱讀

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

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

許久未更。做了幾道二分法的題目練手，發(fā)現(xiàn)這道題已經(jīng)淡忘了，記錄一下。

這道題目的要點在于找inorder的區(qū)間。preStart每增加一次，就對應(yīng)一個新的子樹。每個子樹的根節(jié)點都可以在inorder的中間某處找到，以此為界，左邊是這個根節(jié)點的左子樹，右邊是右子樹。不斷遞歸，得解。

邊界條件需要注意：

若preorder或inorder數(shù)組為空，返回空；

當(dāng)preStart前進到超出preorder末位，或inStart超過inEnd，返回空；

每次創(chuàng)建完根節(jié)點之后，要將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;
    }
}

文章版權(quán)歸作者所有，未經(jīng)允許請勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。

轉(zhuǎn)載請注明本文地址：http://systransis.cn/yun/65932.html

相關(guān)文章

  • [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 評論0 收藏0

  • Construct Binary Tree from Preorder and Inorder Tr

    摘要：解題思路利用遞歸思想，先序遍歷的第一個元素就是根節(jié)點，然后在中序遍歷中尋找該節(jié)點，該節(jié)點左邊的就是左子樹，右邊的是右子樹。 Construct Binary Tree from Preorder and Inorder TraversalGiven preorder and inorder traversal of a tree, construct the binary tree. ...

    tuomao 評論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 評論0 收藏0

  • [LintCode/LeetCode] Binary Tree Serialization

    摘要：這里要注意的是的用法。所以記住，用可以從自動分離出數(shù)組。跳過第一個元素并放入數(shù)組最快捷語句建立的用意記錄處理過的結(jié)點并按處理所有結(jié)點和自己的連接下面先通過判斷，再修改的符號的順序，十分巧妙更輕便的解法 Problem Design an algorithm and write code to serialize and deserialize a binary tree. Writin...

    keithyau 評論0 收藏0

  • [LintCode/LeetCode] Balanced Binary Tree

    摘要：根據(jù)二叉平衡樹的定義，我們先寫一個求二叉樹最大深度的函數(shù)。在主函數(shù)中，利用比較左右子樹的差值來判斷當(dāng)前結(jié)點的平衡性，如果不滿足則返回。 Problem Given a binary tree, determine if it is height-balanced. For this problem, a height-balanced binary tree is defined as...

    morgan 評論0 收藏0

發(fā)表評論

0條評論

最新活動
閱讀需要支付1元查看
<