国产xxxx99真实实拍_久久不雅视频_高清韩国a级特黄毛片_嗯老师别我我受不了了小说

資訊專欄INFORMATION COLUMN

Construct Binary Tree from Preorder and Inorder Tr

tuomao / 1209人閱讀

摘要:解題思路利用遞歸思想,先序遍歷的第一個(gè)元素就是根節(jié)點(diǎn),然后在中序遍歷中尋找該節(jié)點(diǎn),該節(jié)點(diǎn)左邊的就是左子樹,右邊的是右子樹。

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.解題思路
利用遞歸思想,先序遍歷的第一個(gè)元素就是根節(jié)點(diǎn),然后在中序遍歷中尋找該節(jié)點(diǎn),該節(jié)點(diǎn)左邊的就是左子樹,右邊的是右子樹。

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.

解題思路
后序遍歷,所以邏輯和上一題一樣,但是我們要從后序遍歷的最后一個(gè)節(jié)點(diǎn)開始,這樣我們就得先處理右子樹,再處理左子樹。

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;
    }
}

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

轉(zhuǎn)載請(qǐng)注明本文地址:http://m.specialneedsforspecialkids.com/yun/69807.html

相關(guān)文章

  • [LintCode/LeetCode] Construct Binary Tree from Tr

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

    馬忠志 評(píng)論0 收藏0
  • Construct Binary Tree from Traversal

    摘要:思路在的順序里,先,然后再左右。所以根據(jù)可以知道的。接著再分別在和的里面重復(fù)找以及左右的過程。首先的包括和,以及對(duì)應(yīng)的起始和結(jié)束位置,對(duì)應(yīng)的起始和結(jié)束位置。返回值為,因?yàn)槊總€(gè)里要一個(gè),同時(shí)找到它的和,左右節(jié)點(diǎn)通過返回值獲得。同時(shí)的不需要了。 From Preorder and Inorder 思路在preorder的順序里,先root,然后再左右。所以根據(jù)preorder可以知道roo...

    wenshi11019 評(píng)論0 收藏0
  • [Leetcode] Construct Binary Tree from Traversal 根據(jù)

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

    caoym 評(píng)論0 收藏0
  • leetcode449. Serialize and Deserialize BST

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

    Honwhy 評(píng)論0 收藏0
  • [LeetCode-Tree]Binary Tree Inorder & Preorder

    摘要:代碼解題思路先序遍歷,同樣用迭代實(shí)現(xiàn),借助棧。先將根節(jié)點(diǎn)入棧先序遍歷,所以直接出根節(jié)點(diǎn)因?yàn)轫樞蚴歉蠊?jié)點(diǎn),右節(jié)點(diǎn),所以我們?cè)趬簵5臅r(shí)候要先壓右節(jié)點(diǎn),再壓左節(jié)點(diǎn)。所以我們自定義了一個(gè)類,添加了的屬性,來表明該節(jié)點(diǎn)是否已經(jīng)被訪問過了。 Binary Tree Inorder TraversalGiven a binary tree, return the inorder traversa...

    taowen 評(píng)論0 收藏0

發(fā)表評(píng)論

0條評(píng)論

最新活動(dòng)
閱讀需要支付1元查看
<