<cite id="cug02"></cite>

Construct Binary Tree from Preorder and Inorder Tr

tuomao 發布于2019-08-16 10:26 / 1201人閱讀

摘要：解題思路利用遞歸思想，先序遍歷的第一個元素就是根節點，然后在中序遍歷中尋找該節點，該節點左邊的就是左子樹，右邊的是右子樹。

Construct Binary Tree from Preorder and Inorder Traversal
Given preorder and inorder traversal of a tree, construct the binary tree.

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

1.解題思路
利用遞歸思想，先序遍歷的第一個元素就是根節點，然后在中序遍歷中尋找該節點，該節點左邊的就是左子樹，右邊的是右子樹。

2.代碼

public class Solution {
    int curroot=0;
    public TreeNode buildTree(int[] preorder, int[] inorder) {
       return  build(0,inorder.length-1,preorder,inorder);
    }
    private TreeNode build(int instart,int inend,int[] preorder, int[] inorder){
        if(curroot==preorder.length||instart>inend) return null;
        TreeNode root=new TreeNode(preorder[curroot]);
        //find mid in inorder;
        int mid=0;
        for(int i=instart;i<=inend;i++){
            if(inorder[i]==preorder[curroot]){
                mid=i;
                break;
            }
                
        }
        curroot++;
        root.left=build(instart,mid-1,preorder,inorder);
        root.right=build(mid+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.

解題思路
后序遍歷，所以邏輯和上一題一樣，但是我們要從后序遍歷的最后一個節點開始，這樣我們就得先處理右子樹，再處理左子樹。

2.代碼

public class Solution {
    int curroot=0;
    public TreeNode buildTree(int[] inorder, int[] postorder) {
        curroot=postorder.length-1;
        return  build(0,inorder.length-1,inorder,postorder);
    }
    private TreeNode build(int instart,int inend,int[] inorder, int[] postorder){
        if(curroot<0||instart>inend) return null;
        TreeNode root=new TreeNode(postorder[curroot]);
        int mid=0;
        for(int i=instart;i<=inend;i++){
            if(inorder[i]==postorder[curroot]){
                mid=i;
                break;
            }
                
        }
        curroot--;
        root.right=build(mid+1,inend,inorder,postorder);
        root.left=build(instart,mid-1,inorder,postorder);
        
        return root;
    }
}

云服務器 GPU云服務器 binary-tree binary-search-tree Inorder Preorder

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

轉載請注明本文地址：http://specialneedsforspecialkids.com/yun/69807.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
Construct Binary Tree from Traversal

摘要：思路在的順序里，先，然后再左右。所以根據可以知道的。接著再分別在和的里面重復找以及左右的過程。首先的包括和，以及對應的起始和結束位置，對應的起始和結束位置。返回值為，因為每個里要一個，同時找到它的和，左右節點通過返回值獲得。同時的不需要了。 From Preorder and Inorder 思路在preorder的順序里，先root，然后再左右。所以根據preorder可以知道roo...

wenshi11019 2019-08-14 17:11 評論0 收藏0
[Leetcode] Construct Binary Tree from Traversal 根據

摘要：二分法復雜度時間空間思路我們先考察先序遍歷序列和中序遍歷序列的特點。對于中序遍歷序列，根在中間部分，從根的地方分割，前半部分是根的左子樹，后半部分是根的右子樹。 Construct Binary Tree from Preorder and Inorder Traversal Given preorder and inorder traversal of a tree, constru...

caoym 2019-08-14 12:32 評論0 收藏0
leetcode449. Serialize and Deserialize BST

摘要：題目要求將二叉搜索樹序列化和反序列化，序列化是指將樹用字符串的形式表示，反序列化是指將字符串形式的樹還原成原來的樣子。假如二叉搜索樹的節點較多，該算法將會占用大量的額外空間。題目要求 Serialization is the process of converting a data structure or object into a sequence of bits so that...

Honwhy 2019-08-16 16:58 評論0 收藏0
[LeetCode-Tree]Binary Tree Inorder & Preorder

摘要：代碼解題思路先序遍歷，同樣用迭代實現，借助棧。先將根節點入棧先序遍歷，所以直接出根節點因為順序是根，左節點，右節點，所以我們在壓棧的時候要先壓右節點，再壓左節點。所以我們自定義了一個類，添加了的屬性，來表明該節點是否已經被訪問過了。 Binary Tree Inorder TraversalGiven a binary tree, return the inorder traversa...

taowen 2019-08-16 10:26 評論0 收藏0