[LeetCode-Tree]Binary Tree Inorder & Preorder

taowen 發(fā)布于2019-08-16 10:26 / 1464人閱讀

摘要：代碼解題思路先序遍歷，同樣用迭代實現(xiàn)，借助棧。先將根節(jié)點入棧先序遍歷，所以直接出根節(jié)點因為順序是根，左節(jié)點，右節(jié)點，所以我們在壓棧的時候要先壓右節(jié)點，再壓左節(jié)點。所以我們自定義了一個類，添加了的屬性，來表明該節(jié)點是否已經(jīng)被訪問過了。

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.解題思路

這里我們選用迭代來解題，借用壓棧出棧來實現(xiàn)。
1）中序遍歷，左節(jié)點，根，右節(jié)點，所以每次遇到root節(jié)點，我們就將其壓入棧中，然后在判斷它有沒有左節(jié)點，有的話也壓入棧中，直到樹的最左邊的葉子節(jié)點，第一步就結(jié)束了；
2）現(xiàn)在我們開始出棧，每次出棧的節(jié)點肯定不會再有左孩子了，但我們需要判斷它是否有右孩子，如果有，我們要針對右節(jié)點再做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.解題思路

先序遍歷，同樣用迭代實現(xiàn)，借助棧。
1）先將根節(jié)點入棧
2）先序遍歷，所以直接Pop出根節(jié)點
3）因為順序是根，左節(jié)點，右節(jié)點，所以我們在壓棧的時候要先壓右節(jié)點，再壓左節(jié)點。

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.解題思路
后序遍歷，本題比前兩題稍微復雜一點，因為后序遍歷，必然根節(jié)點會被訪問到兩次，一次是入棧，并訪問其左節(jié)點，但還要考慮其是否有右節(jié)點，如果有右節(jié)點必須先輸出右節(jié)點，所以我們不能馬上將根節(jié)點立即出棧。
所以我們自定義了一個類，添加了isVisited的屬性，來表明該節(jié)點是否已經(jīng)被訪問過了。

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

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

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

轉(zhuǎn)載請注明本文地址：http://specialneedsforspecialkids.com/yun/69786.html

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 2019-08-16 10:26 評論0 收藏0
[LintCode/LeetCode] Construct Binary Tree from Tr

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

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

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

摘要：二分法復雜度時間空間思路我們先考察先序遍歷序列和中序遍歷序列的特點。對于中序遍歷序列，根在中間部分，從根的地方分割，前半部分是根的左子樹，后半部分是根的右子樹。 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
Inorder Preorder Postorder

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

caikeal 2019-08-14 17:23 評論0 收藏0