[Leetcode] Binary Tree Traversal 二叉樹(shù)遍歷

RaoMeng 發(fā)布于2019-08-14 12:25 / 3255人閱讀

摘要：棧迭代復(fù)雜度時(shí)間空間遞歸棧空間對(duì)于二叉樹(shù)思路用迭代法做深度優(yōu)先搜索的技巧就是使用一個(gè)顯式聲明的存儲(chǔ)遍歷到節(jié)點(diǎn)，替代遞歸中的進(jìn)程棧，實(shí)際上空間復(fù)雜度還是一樣的。對(duì)于先序遍歷，我們出棧頂節(jié)點(diǎn)，記錄它的值，然后將它的左右子節(jié)點(diǎn)入棧，以此類(lèi)推。

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].

棧迭代 復(fù)雜度

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

思路

用迭代法做深度優(yōu)先搜索的技巧就是使用一個(gè)顯式聲明的Stack存儲(chǔ)遍歷到節(jié)點(diǎn)，替代遞歸中的進(jìn)程棧，實(shí)際上空間復(fù)雜度還是一樣的。對(duì)于先序遍歷，我們pop出棧頂節(jié)點(diǎn)，記錄它的值，然后將它的左右子節(jié)點(diǎn)push入棧，以此類(lèi)推。

代碼

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].

棧迭代 復(fù)雜度

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

思路

用棧中序遍歷沒(méi)有先序遍歷那么直觀，因?yàn)槲覀儾荒荞R上pop出當(dāng)前元素，而要先把它的左子樹(shù)都遍歷完才能pop它自己。所有我們先將將最左邊的所有節(jié)點(diǎn)都push進(jìn)棧，然后再依次pop并記錄值，每pop一個(gè)元素后再看它有沒(méi)有右子樹(shù)，如果右的話，我們?cè)賹⑺挠夜?jié)點(diǎn)和右子樹(shù)中最左邊的節(jié)點(diǎn)都push進(jìn)棧，再依次pop。

代碼

public class Solution {
    public List inorderTraversal(TreeNode root) {
        List res = new LinkedList();
        Stack s = new Stack();
        //先將最左邊的節(jié)點(diǎn)都push進(jìn)棧
        if(root!=null){
            pushAllTheLeft(s, root);
        }
        while(!s.isEmpty()){
            TreeNode curr = s.pop();
            res.add(curr.val);
            //如果有右子樹(shù)，將右節(jié)點(diǎn)和右子樹(shù)的最左邊的節(jié)點(diǎn)都push進(jìn)棧
            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].

棧迭代 復(fù)雜度

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

思路

后序遍歷就不能簡(jiǎn)單的改變pop順序來(lái)實(shí)現(xiàn)了，我們知道根節(jié)點(diǎn)（這里的根節(jié)點(diǎn)不是整個(gè)樹(shù)的根，而是相對(duì)于左右節(jié)點(diǎn)的跟）是在左右節(jié)點(diǎn)都計(jì)算完才計(jì)算的，所以我們會(huì)遇到兩次根節(jié)點(diǎn)，第一次遇到根節(jié)點(diǎn)時(shí)我們將左右節(jié)點(diǎn)加入棧，但不把根節(jié)點(diǎn)pop出去，等到處理完左右節(jié)點(diǎn)后，我們又會(huì)遇到一次根節(jié)點(diǎn)，這時(shí)再計(jì)算根節(jié)點(diǎn)并把它pop出去。為了判斷是第一次還是第二次遇到這個(gè)根節(jié)點(diǎn)，我們可以用一個(gè)數(shù)據(jù)結(jié)構(gòu)把這個(gè)信息封裝進(jìn)去，第一次遇到的時(shí)候?qū)⑵湓O(shè)為已經(jīng)訪問(wèn)了一次，這樣第二次遇到時(shí)發(fā)現(xiàn)已經(jīng)訪問(wèn)了一次，就可以直接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();
            //如果是第二次訪問(wèn)，就計(jì)算并pop該節(jié)點(diǎn)
            if(curr.visited){
                res.add(curr.node.val);
                s.pop();
            } else {
            //如果是第一次訪問(wèn)，就將它的左右節(jié)點(diǎn)加入stack，并設(shè)置其已經(jīng)訪問(wèn)了一次
                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;
        }
    }
}

反向法 復(fù)雜度

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

思路

還有一種更巧妙的方法，因?yàn)楹笮虮闅v的順序是left - right - root，雖然我們不方便直接得到這個(gè)順序，但是它的逆序還是很好得到的，我們可以用root - right - left的順序遍歷樹(shù)，然后反向添加結(jié)果就行了。

代碼

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();
            // 先添加左后添加右，就是先訪問(wèn)右后訪問(wèn)左
            if(curr.left != null) stk.push(curr.left);
            if(curr.right != null) stk.push(curr.right);
            // 反向添加結(jié)果，每次加到最前面
            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]
]

隊(duì)列迭代 復(fù)雜度

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

思路

本題實(shí)質(zhì)是廣度優(yōu)先搜索BFS，而用隊(duì)列可以輕松的以迭代形式實(shí)現(xiàn)它。不過(guò)不同于BFS的是，層序遍歷需要在隊(duì)列中記住每一層的分割點(diǎn)，而B(niǎo)FS不關(guān)心層數(shù)只要遍歷到指定元素就行了。為了記住這個(gè)分割點(diǎn)，我們?cè)谶M(jìn)入下一層之前先記下這一層的元素個(gè)數(shù)N（其實(shí)就是當(dāng)前queue的大小），然后只遍歷N個(gè)節(jié)點(diǎn)（展開(kāi)下一層節(jié)點(diǎn)的同時(shí)queue中會(huì)新加入很多下下一層的節(jié)點(diǎn)）。遍歷完N個(gè)節(jié)點(diǎn)后記錄新的層數(shù)，再進(jìn)入下一層。對(duì)于II，返回的層是逆序的，我們只要在結(jié)果中，每次把下面新一層加到當(dāng)前這層的前面就行了

代碼

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();
            //控制當(dāng)前層的遍歷次數(shù)
            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);
            //對(duì)于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]
]

隊(duì)列迭代 復(fù)雜度

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

思路

ZigZag遍歷時(shí)，奇數(shù)層正序記錄，偶數(shù)層逆序記錄。可以通過(guò)結(jié)果中已有的層數(shù)來(lái)判斷。

代碼

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();
                //根據(jù)結(jié)果中已有的層數(shù)控制正序還是逆序
                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;
    }
}