亚洲中字慕日产2020,大陆极品少妇内射AAAAAA,无码av大香线蕉伊人久久,久久精品国产亚洲av麻豆网站

資訊專(zhuān)欄INFORMATION COLUMN

[LeetCode-Tree]Binary Tree Inorder & Preorder

taowen / 1529人閱讀

摘要：代碼解題思路先序遍歷，同樣用迭代實(shí)現(xiàn)，借助棧。先將根節(jié)點(diǎn)入棧先序遍歷，所以直接出根節(jié)點(diǎn)因?yàn)轫樞蚴歉蠊?jié)點(diǎn)，右節(jié)點(diǎn)，所以我們?cè)趬簵５臅r(shí)候要先壓右節(jié)點(diǎn)，再壓左節(jié)點(diǎn)。所以我們自定義了一個(gè)類(lèi)，添加了的屬性，來(lái)表明該節(jié)點(diǎn)是否已經(jīng)被訪問(wèn)過(guò)了。

Binary Tree Inorder Traversal
Given a binary tree, return the inorder traversal of its nodes" values.

For example:
Given binary tree [1,null,2,3],
1

 2
/

3
return [1,3,2].

1.解題思路

這里我們選用迭代來(lái)解題，借用壓棧出棧來(lái)實(shí)現(xiàn)。
1）中序遍歷，左節(jié)點(diǎn)，根，右節(jié)點(diǎn)，所以每次遇到root節(jié)點(diǎn)，我們就將其壓入棧中，然后在判斷它有沒(méi)有左節(jié)點(diǎn)，有的話也壓入棧中，直到樹(shù)的最左邊的葉子節(jié)點(diǎn)，第一步就結(jié)束了；
2）現(xiàn)在我們開(kāi)始出棧，每次出棧的節(jié)點(diǎn)肯定不會(huì)再有左孩子了，但我們需要判斷它是否有右孩子，如果有，我們要針對(duì)右節(jié)點(diǎn)再做step1的操作。

2.代碼

public class Solution {
    Stack s=new Stack();
    public List inorderTraversal(TreeNode root) {
        List res =new ArrayList();
        if(root==null) return res;
        pushLeft(root);
        while(!s.empty()){
            TreeNode pnode=s.pop();
            res.add(pnode.val);
            if(pnode.right!=null){
                pushLeft(pnode.right);
            }
        }
        return res;
    }
    private void pushLeft(TreeNode root){
        TreeNode node=root.left;
        s.push(root);
        while(node!=null){
            s.push(node);
            node=node.left;
        }
    }
}

Binary Tree Preorder Traversal
Given a binary tree, return the preorder traversal of its nodes" values.

For example:
Given binary tree {1,#,2,3},
   1
    
     2
    /
   3
return [1,2,3].

Note: Recursive solution is trivial, could you do it iteratively?

1.解題思路

先序遍歷，同樣用迭代實(shí)現(xiàn)，借助棧。
1） 先將根節(jié)點(diǎn)入棧
2）先序遍歷，所以直接Pop出根節(jié)點(diǎn)
3）因?yàn)轫樞蚴歉?，左?jié)點(diǎn)，右節(jié)點(diǎn)，所以我們?cè)趬簵５臅r(shí)候要先壓右節(jié)點(diǎn)，再壓左節(jié)點(diǎn)。

public class Solution {
    public List preorderTraversal(TreeNode root) {
        List res=new ArrayList();
        if(root==null) return res;
        Stack s=new Stack();
        s.push(root);
        while(!s.empty()){
            TreeNode node=s.pop();
            res.add(node.val);
            if(node.right!=null)
                s.push(node.right);
            if(node.left!=null)
                s.push(node.left);
        }
        return res;
    }
}

Binary Tree Postorder Traversal
Given a binary tree, return the postorder traversal of its nodes" values.

For example:

Given binary tree {1,#,2,3},
   1
    
     2
    /
   3

return [3,2,1].

1.解題思路
后序遍歷，本題比前兩題稍微復(fù)雜一點(diǎn)，因?yàn)楹笮虮闅v，必然根節(jié)點(diǎn)會(huì)被訪問(wèn)到兩次，一次是入棧，并訪問(wèn)其左節(jié)點(diǎn)，但還要考慮其是否有右節(jié)點(diǎn)，如果有右節(jié)點(diǎn)必須先輸出右節(jié)點(diǎn)，所以我們不能馬上將根節(jié)點(diǎn)立即出棧。
所以我們自定義了一個(gè)類(lèi)，添加了isVisited的屬性，來(lái)表明該節(jié)點(diǎn)是否已經(jīng)被訪問(wèn)過(guò)了。

2.代碼

public class Solution {
    Stack s=new Stack();
    public List postorderTraversal(TreeNode root) {
        List res=new ArrayList();
        if(root==null) return res;
        
        pushLeft(new DefinedTreeNode(root,false));
        while(!s.empty()){
            DefinedTreeNode dt=s.peek();
            if(dt.node.right==null||dt.isVisited){
                s.pop();
                res.add(dt.node.val);
            }
            else{
                dt.isVisited=true;
                pushLeft(new DefinedTreeNode(dt.node.right,false));
            }
            
            
        }
        return res;
    }
    private void pushLeft(DefinedTreeNode root){
        s.push(root);
        DefinedTreeNode dt=new DefinedTreeNode(root.node.left,false);
        while(dt.node!=null){
            s.push(dt);
            dt=new DefinedTreeNode(dt.node.left,false);
        }
    }
    class DefinedTreeNode {
        TreeNode node;
        boolean isVisited;
        DefinedTreeNode(TreeNode node, boolean isVisited){
            this.node=node;
            this.isVisited=isVisited;
        }
    }
}

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

轉(zhuǎn)載請(qǐng)注明本文地址：http://www.ezyhdfw.cn/yun/69786.html

相關(guān)文章

  • Construct Binary Tree from Preorder and Inorder Tr

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

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

  • [LintCode/LeetCode] Construct Binary Tree from Tr

    摘要：做了幾道二分法的題目練手，發(fā)現(xiàn)這道題已經(jīng)淡忘了，記錄一下。這道題目的要點(diǎn)在于找的區(qū)間。邊界條件需要注意若或數(shù)組為空，返回空當(dāng)前進(jìn)到超出末位，或超過(guò)，返回空每次創(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ù)找以及左右的過(guò)程。首先的包括和，以及對(duì)應(yīng)的起始和結(jié)束位置，對(duì)應(yīng)的起始和結(jié)束位置。返回值為，因?yàn)槊總€(gè)里要一個(gè)，同時(shí)找到它的和，左右節(jié)點(diǎn)通過(guò)返回值獲得。同時(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ì)于中序遍歷序列，根在中間部分，從根的地方分割，前半部分是根的左子樹(shù)，后半部分是根的右子樹(shù)。 Construct Binary Tree from Preorder and Inorder Traversal Given preorder and inorder traversal of a tree, constru...

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

  • Inorder Preorder Postorder

    摘要：題目鏈接參考這篇文章鏈接題目鏈接還是一樣的，用，或者保存和。題目鏈接題目鏈接按照的順序最后再一下。 Inorder Binary Tree Inorder Traversal lc題目鏈接：https://leetcode.com/problems... recursion： public class Solution { public List inorderTraversa...

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

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

0條評(píng)論

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