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

資訊專欄INFORMATION COLUMN

[Leetcode] Binary Tree Traversal 二叉樹遍歷

RaoMeng / 3258人閱讀

摘要：棧迭代復雜度時間空間遞歸?？臻g對于二叉樹思路用迭代法做深度優先搜索的技巧就是使用一個顯式聲明的存儲遍歷到節點，替代遞歸中的進程棧，實際上空間復雜度還是一樣的。對于先序遍歷，我們出棧頂節點，記錄它的值，然后將它的左右子節點入棧，以此類推。

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].
棧迭代 復雜度

時間 O(b^(h+1)-1) 空間 O(h) 遞歸?？臻g 對于二叉樹b=2

思路

用迭代法做深度優先搜索的技巧就是使用一個顯式聲明的Stack存儲遍歷到節點，替代遞歸中的進程棧，實際上空間復雜度還是一樣的。對于先序遍歷，我們pop出棧頂節點，記錄它的值，然后將它的左右子節點push入棧，以此類推。

代碼 
public class Solution {
    public List preorderTraversal(TreeNode root) {
        Stack s = new Stack();
        List res = new LinkedList();
        if(root!=null) s.push(root);
        while(!s.isEmpty()){
            TreeNode curr = s.pop();
            res.add(curr.val);
            if(curr.right!=null) s.push(curr.right);
            if(curr.left!=null) s.push(curr.left);
        }
        return res;
    }
}
Binary Tree Inorder Traversal 
Given a binary tree, return the inorder traversal of its nodes" values.


For example: Given binary tree {1,#,2,3},


   1
    
     2
    /
   3



return [1,3,2].
棧迭代 復雜度

時間 O(b^(h+1)-1) 空間 O(h) 遞歸?？臻g 對于二叉樹b=2

思路

用棧中序遍歷沒有先序遍歷那么直觀，因為我們不能馬上pop出當前元素，而要先把它的左子樹都遍歷完才能pop它自己。所有我們先將將最左邊的所有節點都push進棧，然后再依次pop并記錄值，每pop一個元素后再看它有沒有右子樹，如果右的話，我們再將它的右節點和右子樹中最左邊的節點都push進棧，再依次pop。

代碼 
public class Solution {
    public List inorderTraversal(TreeNode root) {
        List res = new LinkedList();
        Stack s = new Stack();
        //先將最左邊的節點都push進棧
        if(root!=null){
            pushAllTheLeft(s, root);
        }
        while(!s.isEmpty()){
            TreeNode curr = s.pop();
            res.add(curr.val);
            //如果有右子樹，將右節點和右子樹的最左邊的節點都push進棧
            if(curr.right != null){
                pushAllTheLeft(s, curr.right);
            }
        }
        return res;
    }
    
    private void pushAllTheLeft(Stack s, TreeNode root){
        s.push(root);
        while(root.left!=null){
            root = root.left;
            s.push(root);
        }
    }
}
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].
棧迭代 復雜度

時間 O(b^(h+1)-1) 空間 O(h) 遞歸?？臻g 對于二叉樹b=2

思路

后序遍歷就不能簡單的改變pop順序來實現了，我們知道根節點（這里的根節點不是整個樹的根，而是相對于左右節點的跟）是在左右節點都計算完才計算的，所以我們會遇到兩次根節點，第一次遇到根節點時我們將左右節點加入棧，但不把根節點pop出去，等到處理完左右節點后，我們又會遇到一次根節點，這時再計算根節點并把它pop出去。為了判斷是第一次還是第二次遇到這個根節點，我們可以用一個數據結構把這個信息封裝進去，第一次遇到的時候將其設為已經訪問了一次，這樣第二次遇到時發現已經訪問了一次，就可以直接pop了。

代碼 
public class Solution {
    public List postorderTraversal(TreeNode root) {
        Stack s = new Stack();
        List res = new LinkedList();
        if(root!=null) s.push(new PowerNode(root, false));
        while(!s.isEmpty()){
            PowerNode curr = s.peek();
            //如果是第二次訪問，就計算并pop該節點
            if(curr.visited){
                res.add(curr.node.val);
                s.pop();
            } else {
            //如果是第一次訪問，就將它的左右節點加入stack，并設置其已經訪問了一次
                if(curr.node.right!=null) s.push(new PowerNode(curr.node.right, false));
                if(curr.node.left!=null) s.push(new PowerNode(curr.node.left, false));
                curr.visited = true;
            }
        }
        return res;
    }
    
    private class PowerNode {
        TreeNode node;
        boolean visited;
        public PowerNode(TreeNode n, boolean v){
            this.node = n;
            this.visited = v;
        }
    }
}
反向法 復雜度

時間 O(b^(h+1)-1) 空間 O(h) 遞歸棧空間 對于二叉樹b=2

思路

還有一種更巧妙的方法，因為后序遍歷的順序是left - right - root，雖然我們不方便直接得到這個順序，但是它的逆序還是很好得到的，我們可以用root - right - left的順序遍歷樹，然后反向添加結果就行了。

代碼 
public class Solution {
    public List postorderTraversal(TreeNode root) {
        Stack stk = new Stack();
        if(root != null) stk.push(root);
        LinkedList res = new LinkedList();
        while(!stk.isEmpty()){
            TreeNode curr = stk.pop();
            // 先添加左后添加右，就是先訪問右后訪問左
            if(curr.left != null) stk.push(curr.left);
            if(curr.right != null) stk.push(curr.right);
            // 反向添加結果，每次加到最前面
            res.offerFirst(curr.val);
        }
        return res;
    }
}
Binary Tree Level Order Traversal I && II 
Given a binary tree, return the bottom-up level order traversal of its nodes" values. (ie, from left to right, level by level from leaf to root).


For example: Given binary tree {3,9,20,#,#,15,7},


    3
   / 
  9  20
    /  
   15   7



return its bottom-up level order traversal as: (II)


[
  [15,7],
  [9,20],
  [3]
]


return its level order traversal as: (I)


[
  [3],
  [9,20],
  [15,7]
]
隊列迭代 復雜度

時間 O(b^(h+1)-1) 空間 O(b^h)

思路

本題實質是廣度優先搜索BFS，而用隊列可以輕松的以迭代形式實現它。不過不同于BFS的是，層序遍歷需要在隊列中記住每一層的分割點，而BFS不關心層數只要遍歷到指定元素就行了。為了記住這個分割點，我們在進入下一層之前先記下這一層的元素個數N（其實就是當前queue的大?。缓笾槐闅vN個節點（展開下一層節點的同時queue中會新加入很多下下一層的節點）。遍歷完N個節點后記錄新的層數，再進入下一層。對于II，返回的層是逆序的，我們只要在結果中，每次把下面新一層加到當前這層的前面就行了

代碼 
public class Solution {
    public List> levelOrder(TreeNode root) {
        List> res = new LinkedList>();
        Queue q = new LinkedList();
        if(root != null) q.offer(root);
        while(!q.isEmpty()){
            int size = q.size();
            List level = new LinkedList();
            //控制當前層的遍歷次數
            for(int i =0; i < size; i++){
                TreeNode curr = q.poll();
                level.add(curr.val);
                if(curr.left!=null) q.offer(curr.left);
                if(curr.right!=null) q.offer(curr.right);
            }
            res.add(level);
            //對于II， 我們要逆序加入
            //res.add(0, level)
        }
        return res;
    }
}
Binary Tree Zigzag Level Order Traversal 
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).


For example: Given binary tree {3,9,20,#,#,15,7},


    3
   / 
  9  20
    /  
   15   7



return its zigzag level order traversal as:


[
  [3],
  [20,9],
  [15,7]
]
隊列迭代 復雜度

時間 O(b^(h+1)-1) 空間 O(b^h)

思路

ZigZag遍歷時，奇數層正序記錄，偶數層逆序記錄?？梢酝ㄟ^結果中已有的層數來判斷。

代碼 
public class Solution {
    public List> zigzagLevelOrder(TreeNode root) {
        List> res = new LinkedList>();
        Queue q = new LinkedList();
        if(root != null) q.offer(root);
        while(!q.isEmpty()){
            int size = q.size();
            List level = new LinkedList();
            for(int i =0; i < size; i++){
                TreeNode curr = q.poll();
                //根據結果中已有的層數控制正序還是逆序
                if(res.size() % 2 == 0){
                    level.add(curr.val);
                } else {
                    level.add(0,curr.val);
                }
                if(curr.left!=null) q.offer(curr.left);
                if(curr.right!=null) q.offer(curr.right);
            }
            res.add(level);
        }
        return res;
    }
}

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

轉載請注明本文地址：http://m.specialneedsforspecialkids.com/yun/64468.html

相關文章

  • LeetCode 之 JavaScript 解答第94題 —— 二叉樹的中序遍歷

    摘要：小鹿題目二叉樹中序遍歷給定一個二叉樹，返回它的中序遍歷。通常遞歸的方法解決二叉樹的遍歷最方便不過，但是我還是喜歡增加點難度，用一般的迭代循環來實現。 Time：2019/4/25Title:Binary Tree Inorder TraversalDifficulty: MediumAuthor:小鹿 題目：Binary Tree Inorder Traversal（二叉樹中序遍歷...

    Jason 評論0 收藏0

  • leetcode-102-Binary Tree Level Order Traversal

    102. 二叉樹的層次遍歷 題目描述 給定一個二叉樹，返回其按層次遍歷的節點值。 （即zhucengde，從左到右訪問）。 例如: 給定二叉樹: [3,9,20,null,null,15,7], 3 / 9 20 / 15 7 返回其層次遍歷結果為： [ [3], [9,20], [15,7] ] class Solution: def le...

    widuu 評論0 收藏0

  • leetcode講解--94. Binary Tree Inorder Traversal

    摘要：題目地址嗯，經典的題目，中序遍歷二叉樹。代碼如下中序遍歷先序遍歷后序遍歷是不是簡單的不要不要的，遞歸就是這么美。右孩子后壓棧全部釋放出來嗯，總的來說用迭代遍歷確實燒腦，沒什么性能上的特殊需求還是用遞歸寫法吧，對程序員友好哦。 94. Binary Tree Inorder Traversal Given a binary tree, return the inorder travers...

    henry14 評論0 收藏0

  • leetcode-145-Binary Tree Postorder Traversal

    摘要：棧的意義價值具有時間性，先進后出。比如遞歸的后序遍歷，先序遍歷，二叉樹的按層次打印。根據需求不同，在中暫時儲存的元素單元也不同，元素的先后順序也不同。應用對順序有要求的數據。 stack 棧的意義價值： 具有時間性，先進后出。 所以具有時間關聯順序的元素可以通過這個時間。 比如遞歸的后序遍歷，先序遍歷， 二叉樹的按層次打印。 根據需求不同，在stack中暫時儲存的元素...

    Pandaaa 評論0 收藏0

發表評論

0條評論

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