前言

二叉樹遍歷是非常經典的算法題，也是二叉樹的一道基礎算法題。

但是在平常的筆試面試中，其出現的頻率其實并不是特別的高，我推測是這種題目相對來說比較基礎，算是一個基礎知識點。

比如劍指offer中出現的后序遍歷題目，是給出一個數字序列，讓你判斷是不是平衡二叉樹后序遍歷序列，這樣出題的難度比直接讓你寫后序遍歷難很多。

但是，二叉樹遍歷容易嗎？在遞歸方法下，前中后序遍歷都是一個思路，理解起來也比較容易。

但是只是用迭代的話，二叉樹遍歷其實是有難度的！，這也是為什么LeetCode會在這三題題目的下方寫出進階: 遞歸算法很簡單，你可以通過迭代算法完成嗎？這句話了。

本文的主要內容如下：

題目定義：
- 上篇：二叉樹前序、中序、后序遍歷
- 下篇：層序遍歷、其他遍歷相關題型
解題思路：遞歸 + 迭代+ 莫里斯Morris遍歷
解題代碼：Java + Python

注1：本文中的解題思路會盡量的全面，但是解題方法千變萬化，有很多奇技淫巧我不會去介紹，大家有興趣可以自行擴展學習。

注2：本文中的代碼會盡量簡單，易懂，并不會去追求極致的寫法（比如：在一行內完成，使用各種非正式的庫等）。

正文

二叉樹的定義

最多有兩棵子樹的樹被稱為二叉樹

image

二叉樹下還有很多種特殊的二叉樹，下方簡單介紹幾種常用的。

滿二叉樹

二叉樹中所有非葉子結點的度都是2，且葉子結點都在同一層次上

image

完全二叉樹（可以不滿）

如果一個二叉樹與滿二叉樹前m個節(jié)點的結構相同，這樣的二叉樹被稱為完全二叉樹。也就是說，如果把滿二叉樹從右至左、從下往上刪除一些節(jié)點，剩余的結構就構成完全二叉樹。

image

二叉搜索樹

二叉查找樹（BinarySearch Tree，也叫二叉搜索樹，或稱二叉排序樹Binary Sort Tree）或者是一棵空樹，或者是具有下列性質的二叉樹：

若它的左子樹不空，則左子樹上所有結點的值均小于它的根結點的值；
若它的右子樹不空，則右子樹上所有結點的值均大于它的根結點的值；
它的左、右子樹也分別為二叉排序樹

image

二叉樹前中后序遍歷

遍歷方法

前序遍歷：根結點 ---> 左子樹 ---> 右子樹

中序遍歷：左子樹---> 根結點 ---> 右子樹

后序遍歷：左子樹 ---> 右子樹 ---> 根結點

題目介紹

前序遍歷

LeetCode題目地址：

https://leetcode-cn.com/problems/binary-tree-preorder-traversal/

輸入: [1,null,2,3]  
   1
    \
     2
    /
   3 

輸出: [1,2,3]

中序遍歷

LeetCode題目地址：

https://leetcode-cn.com/problems/binary-tree-inorder-traversal/

輸入: [1,null,2,3]
   1
    \
     2
    /
   3

輸出: [1,3,2]

后序遍歷

LeetCode題目地址：

https://leetcode-cn.com/problems/binary-tree-postorder-traversal/

輸入: [1,null,2,3]  
   1
    \
     2
    /
   3 

輸出: [3,2,1]

解題思路詳解與代碼實現

二叉樹的前中后序遍歷，主要就是兩種思路，一種是遞歸，一種是迭代。

如果看到這里還沒有感覺，不用擔心，先直接往下看，第一個代碼（前序遍歷的遞歸思路）會幫助你提升感覺。

遞歸思路

遞歸思路是最容易理解的思路，并且前中后序遍歷都相同。

比如前序遍歷，在遞歸的函數里，先往結果數組里加入根節(jié)點，然后加入根節(jié)點的左節(jié)點，然后加入根節(jié)點的右節(jié)點。最后所有遞歸的函數運行完畢，結果集就已經完成了。

中序和后序的思路相同，就不再贅述了。

前序遍歷

Java：

class Solution {
    public List<Integer> preorderTraversal(TreeNode root) {
            List<Integer> result = new ArrayList<>();
            if (root == null) {
                return result;
            }
            preorder(root, result);
            return result;
        }
    
    private static List<Integer> preorder(TreeNode root, List<Integer> result) {
        if (root != null) {
            result.add(root.val);
            preorder(root.left, result);
            preorder(root.right, result);
        }
        return result;
    }
}

Python：

class Solution(object):
    def _preorderTraversal(self, root, result):
        if root:
            result.append(root.val)
            self._preorderTraversal(root.left, result)
            self._preorderTraversal(root.right, result)
    def preorderTraversal(self, root):
        """
        :type root: TreeNode
        :rtype: List[int]
        """
        if root == None:
            return []
        result = []
        self._preorderTraversal(root, result)
        return result

中序遍歷

Java：

class Solution {
    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> result = new ArrayList<>();
        if (root == null) {
            return result;
        }
        result = inorder(root, result);
        return result;
    }

    private static List<Integer> inorder(TreeNode root, List<Integer> result) {
        if (root != null) {
            inorder(root.left, result);
            result.add(root.val);
            inorder(root.right, result);
        }
        return result;
    }
}

Python：

class Solution(object):
    def generate(self, root, result):
        if root:
            self.inorder(root.left, list)
            result.append(root.val)
            self.inorder(root.right, list)
    def inorderTraversal(self, root):
        """
        :type root: TreeNode
        :rtype: List[int]
        """
        if not root:
            return []
        result = []
        self.generate(root, result)
        return result

后序遍歷

Java：

class Solution {
    public List<Integer> postorderTraversal(TreeNode root) {
        List<Integer> result = new ArrayList<>();
        if (root == null) {
            return result;
        }
        result = postorder(root, result);
        return result;
    }

    private static List<Integer> postorder(TreeNode root, List<Integer> result) {
        if (root != null) {
            postorder(root.left, result);
            postorder(root.right, result);
            result.add(root.val);
        }
        return result;
    }
}

Python：

class Solution(object):
    
    def _postorderTraversal(self, root, result):
        if root:
            self._postorderTraversal(root.left, result)
            self._postorderTraversal(root.right, result)
            result.append(root.val)
    def postorderTraversal(self, root):
        """
        :type root: TreeNode
        :rtype: List[int]
        """
        if root == None:
            return []
        result = []
        self._postorderTraversal(root, result)
        return result

迭代思路

前序遍歷

我們需要一個棧來完成遍歷。

1.根節(jié)點入棧

2.取出節(jié)點，值加入結果，然后先加右，后加左。

3.重復2

這樣就得到了根節(jié)點——左子樹——右子樹的遍歷結果集。

Java：

來自官方題解

LinkedList<TreeNode> stack = new LinkedList<>();
    LinkedList<Integer> output = new LinkedList<>();
    if (root == null) {
      return output;
    }

    stack.add(root);
    while (!stack.isEmpty()) {
      TreeNode node = stack.pollLast();
      output.add(node.val);
      if (node.right != null) {
        stack.add(node.right);
      }
      if (node.left != null) {
        stack.add(node.left);
      }
    }
    return output;
  }

Python：

class Solution(object):
    def preorderTraversal(self, root):
        """
        :type root: TreeNode
        :rtype: List[int]
        """
        ret = []
        stack = [root]
        while stack:
            node = stack.pop()
            if node:
                ret.append(node.val)
                if node.right:
                    stack.append(node.right)
                if node.left:
                    stack.append(node.left)
        return ret

中序遍歷

還是使用一個棧來解決問題。

步驟如下：

                    　1

　　　　　　　　　　/　  \

　　　　　　　　   2　　  3

　　　　　　     /   \　 /   \

　　　　　　　  4     5  6    7

我們將根節(jié)點1入棧，如果有左孩子，依次入棧，那么入棧順序為：1，2，4。由于4的左子樹為空，停止入棧，此時棧為{1，2，4}。
此時將4出棧，并遍歷4，由于4也沒有右孩子，那么根據中序遍歷的規(guī)則，我們顯然應該繼續(xù)遍歷4的父親2，情況是這樣。所以我們繼續(xù)將2出棧并遍歷2，2存在右孩子，將5入棧，此時棧為{1，5}。
5沒有孩子，則將5出棧并遍歷5，這也符合中序遍歷的規(guī)則。此時棧為{1}。
1有右孩子，則將1出棧并遍歷1，然后將右孩子3入棧，并繼續(xù)以上三個步驟即可。

棧的變化過程：{1}->{1,2}->{1,2,4}->{1,2}->{1}->{1,5}->{1}->{}->{3}->{3,6}->{3}->{}->{7}->{}。

總結：從根節(jié)點遍歷，先放入所有有左孩子的節(jié)點直到沒有，然后出棧，出棧的時候就將出棧的數字放入結果集，然后看其有沒有右孩子，有的話右孩子入棧。

Java：

官方題解

public class Solution {

    public List <Integer> inorderTraversal(TreeNode root) {
        List<Integer> res = new ArrayList<>();
        Stack<TreeNode> stack = new Stack<>();
        
        TreeNode curr = root;
        while (curr != null || !stack.isEmpty()) {
            while (curr != null) {
                stack.push(curr);
                curr = curr.left;
            }
            curr = stack.pop();
            res.add(curr.val);
            curr = curr.right;
        }
        return res;
    }
}

Python：

class Solution:
    # @param root, a tree node
    # @return a list of integers
    def inorderTraversal(self, root):
        result = []
        stack = []
        while root or stack:
            if root:
                stack.append(root)
                root = root.left
            else:
                root = stack.pop()
                result.append(root.val)
                root = root.right
        return result

后序遍歷

將數組輸出為右子樹-左子樹-根節(jié)點。最后，再將數組倒序輸出，形成后序遍歷。這樣代碼并不用很繁瑣，也能做完迭代。

是不是似曾相識，沒錯，和前序遍歷的迭代幾乎一樣，僅僅是先放右節(jié)點再放左節(jié)點變成了先放左節(jié)點再放右節(jié)點，然后倒序輸出。

Java：

class Solution {
  public List<Integer> postorderTraversal(TreeNode root) {
    LinkedList<TreeNode> stack = new LinkedList<>();
    LinkedList<Integer> output = new LinkedList<>();
    
    if (root == null) {
      return output;
    }

    stack.add(root);
    while (!stack.isEmpty()) {
      TreeNode node = stack.pollLast();
      output.addFirst(node.val);
      if (node.left != null) {
        stack.add(node.left);
      }
      if (node.right != null) {
        stack.add(node.right);
      }
    }
    return output;
  }
}

Python：

class Solution(object):
    def postorderTraversal(self, root):
        """
        :type root: TreeNode
        :rtype: List[int]
        """
        if root is None:
            return []
        ret = []
        stack = [root]
        while stack:
            node = stack.pop()
            if node:
                ret.append(node.val)
                if node.left:
                    stack.append(node.left)
                if node.right:
                    stack.append(node.right)
        return ret[::-1]

所以迭代方式，前后序是非常類似的，中序遍歷可能需要單獨理解下。

莫里斯遍歷

二叉樹常規(guī)的遍歷方法是用遞歸來實現的，這種方法一般都需要O(n)的空間復雜度和O(n)的時間復雜度。而Morris方法實現的是O(1)的空間復雜度和O(n)的時間復雜度。

我們知道，遍歷二叉樹時，最大的難點在于，遍歷到子節(jié)點的時候怎樣重新返回到父節(jié)點（假設節(jié)點中沒有指向父節(jié)點的p指針），由于不能用棧作為輔助空間。(不然就是普通迭代方法)。

為了解決這個問題，Morris方法用到了線索二叉樹（threaded binary tree）的概念。在Morris方法中不需要為每個節(jié)點額外分配指針指向其前驅（predecessor）和后繼節(jié)點（successor），只需要利用葉子節(jié)點中的左右空指針指向某種順序遍歷下的前驅節(jié)點或后繼節(jié)點就可以了。

聽不懂沒關系，下面使用中序遍歷作為例子來理解莫里斯遍歷到底是什么意思，例子來自LeetCode官方題解：

中序遍歷

Step 1: 將當前節(jié)點current初始化為根節(jié)點
Step 2: While current不為空，

若current沒有左子節(jié)點
   a. 將current添加到輸出
   b. 進入右子樹，亦即, current = current.right
否則
   a. 在current的左子樹中，令current成為最右側節(jié)點的右子節(jié)點
   b. 進入左子樹，亦即，current = current.left

首先，1 是根節(jié)點，所以將 current 初始化為 1。1 有左子節(jié)點 2，current 的左子樹是

     2
    / \
   4   5

在此左子樹中最右側的節(jié)點是 5，于是將 current(1) 作為 5 的右子節(jié)點。令 current = cuurent.left (current = 2)。現在二叉樹的形狀為:

對于 current(2)，其左子節(jié)點為4，我們可以繼續(xù)上述過程

Java：

class Solution {
    public List < Integer > inorderTraversal(TreeNode root) {
        List < Integer > res = new ArrayList < > ();
        TreeNode curr = root;
        TreeNode pre;
        while (curr != null) {
            if (curr.left == null) {
                res.add(curr.val);
                curr = curr.right; // move to next right node
            } else { // has a left subtree
                pre = curr.left;
                while (pre.right != null) { // find rightmost
                    pre = pre.right;
                }
                pre.right = curr; // put cur after the pre node
                TreeNode temp = curr; // store cur node
                curr = curr.left; // move cur to the top of the new tree
                temp.left = null; // original cur left be null, avoid infinite loops
            }
        }
        return res;
    }
}

前序遍歷

理解了中序遍歷，前序和后序遍歷相對來說也就更容易理解了。所以前序和后序貼了思路，代碼我也沒自己寫后submit，在這里就不放了。

算法的思路是從當前節(jié)點向下訪問先序遍歷的前驅節(jié)點，每個前驅節(jié)點都恰好被訪問兩次。

首先從當前節(jié)點開始，向左孩子走一步然后沿著右孩子一直向下訪問，直到到達一個葉子節(jié)點（當前節(jié)點的中序遍歷前驅節(jié)點），所以我們更新輸出并建立一條偽邊 predecessor.right = root 更新這個前驅的下一個點。如果我們第二次訪問到前驅節(jié)點，由于已經指向了當前節(jié)點，我們移除偽邊并移動到下一個頂點。

后序遍歷

后續(xù)遍歷稍顯復雜，需要建立一個臨時節(jié)點dump，令其左孩子是root。并且還需要一個子過程，就是倒序輸出某兩個節(jié)點之間路徑上的各個節(jié)點。

步驟：

當前節(jié)點設置為臨時節(jié)點dump。

如果當前節(jié)點的左孩子為空，則將其右孩子作為當前節(jié)點。

如果當前節(jié)點的左孩子不為空，在當前節(jié)點的左子樹中找到當前節(jié)點在中序遍歷下的前驅節(jié)點。

a) 如果前驅節(jié)點的右孩子為空，將它的右孩子設置為當前節(jié)點。當前節(jié)點更新為當前節(jié)點的左孩子。

b) 如果前驅節(jié)點的右孩子為當前節(jié)點，將它的右孩子重新設為空。倒序輸出從當前節(jié)點的左孩子到該前驅節(jié)點這條路徑上的所有節(jié)點。當前節(jié)點更新為當前節(jié)點的右孩子。

重復以上1、2直到當前節(jié)點為空。

參考

https://leetcode-cn.com/problems/binary-tree-preorder-traversal/solution/leetcodesuan-fa-xiu-lian-dong-hua-yan-shi-xbian-2/
https://www.cnblogs.com/AnnieKim/archive/2013/06/15/morristraversal.html
https://blog.csdn.net/softwarex4/article/details/95986102

色偷偷精品伊人,欧洲久久精品,欧美综合婷婷骚逼,国产AV主播,国产最新探花在线,九色在线视频一区,伊人大交九欧美,1769亚洲,黄色成人av

【算法】二叉樹遍歷算法總結：前序中序后序遍歷

【算法】二叉樹遍歷算法總結：前序中序后序遍歷

前言

正文

二叉樹的定義

滿二叉樹

完全二叉樹（可以不滿）

二叉搜索樹

二叉樹前中后序遍歷

遍歷方法

題目介紹

前序遍歷

中序遍歷

后序遍歷

解題思路詳解與代碼實現

遞歸思路

前序遍歷

中序遍歷

后序遍歷

迭代思路

前序遍歷

中序遍歷

后序遍歷

莫里斯遍歷

中序遍歷

前序遍歷

后序遍歷

參考

相關閱讀更多精彩內容

友情鏈接更多精彩內容

色偷偷精品伊人,欧洲久久精品,欧美综合婷婷骚逼,国产AV主播,国产最新探花在线,九色在线视频一区,伊人大交九 欧美,1769亚洲,黄色成人av

【算法】二叉樹遍歷算法總結：前序中序后序遍歷

前言

正文

二叉樹的定義

滿二叉樹

完全二叉樹（可以不滿）

二叉搜索樹

二叉樹前中后序遍歷

遍歷方法

題目介紹

前序遍歷

中序遍歷

后序遍歷

解題思路詳解與代碼實現

遞歸思路

前序遍歷

中序遍歷

后序遍歷

迭代思路

前序遍歷

中序遍歷

后序遍歷

莫里斯遍歷

中序遍歷

前序遍歷

后序遍歷

參考

相關閱讀更多精彩內容

友情鏈接更多精彩內容

色偷偷精品伊人,欧洲久久精品,欧美综合婷婷骚逼,国产AV主播,国产最新探花在线,九色在线视频一区,伊人大交九欧美,1769亚洲,黄色成人av