前言

二叉樹(shù)遍歷是非常經(jīng)典的算法題，也是二叉樹(shù)的一道基礎(chǔ)算法題。

但是在平常的筆試面試中，其出現(xiàn)的頻率其實(shí)并不是特別的高，我推測(cè)是這種題目相對(duì)來(lái)說(shuō)比較基礎(chǔ)，算是一個(gè)基礎(chǔ)知識(shí)點(diǎn)。

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

但是，二叉樹(shù)遍歷容易嗎？在遞歸方法下，前中后序遍歷都是一個(gè)思路，理解起來(lái)也比較容易。

但是只是用迭代的話，二叉樹(shù)遍歷其實(shí)是有難度的！，這也是為什么LeetCode會(huì)在這三題題目的下方寫(xiě)出進(jìn)階: 遞歸算法很簡(jiǎn)單，你可以通過(guò)迭代算法完成嗎？這句話了。

本文的主要內(nèi)容如下：

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

注1：本文中的解題思路會(huì)盡量的全面，但是解題方法千變?nèi)f化，有很多奇技淫巧我不會(huì)去介紹，大家有興趣可以自行擴(kuò)展學(xué)習(xí)。

注2：本文中的代碼會(huì)盡量簡(jiǎn)單，易懂，并不會(huì)去追求極致的寫(xiě)法（比如：在一行內(nèi)完成，使用各種非正式的庫(kù)等）。

正文

二叉樹(shù)的定義

最多有兩棵子樹(shù)的樹(shù)被稱為二叉樹(shù)

image

二叉樹(shù)下還有很多種特殊的二叉樹(shù)，下方簡(jiǎn)單介紹幾種常用的。

滿二叉樹(shù)

二叉樹(shù)中所有非葉子結(jié)點(diǎn)的度都是2，且葉子結(jié)點(diǎn)都在同一層次上

image

完全二叉樹(shù)（可以不滿）

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

image

二叉搜索樹(shù)

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

若它的左子樹(shù)不空，則左子樹(shù)上所有結(jié)點(diǎn)的值均小于它的根結(jié)點(diǎn)的值；
若它的右子樹(shù)不空，則右子樹(shù)上所有結(jié)點(diǎn)的值均大于它的根結(jié)點(diǎn)的值；
它的左、右子樹(shù)也分別為二叉排序樹(shù)

image

二叉樹(shù)前中后序遍歷

遍歷方法

前序遍歷：根結(jié)點(diǎn) ---> 左子樹(shù) ---> 右子樹(shù)

中序遍歷：左子樹(shù)---> 根結(jié)點(diǎn) ---> 右子樹(shù)

后序遍歷：左子樹(shù) ---> 右子樹(shù) ---> 根結(jié)點(diǎn)

題目介紹

前序遍歷

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]

解題思路詳解與代碼實(shí)現(xiàn)

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

如果看到這里還沒(méi)有感覺(jué)，不用擔(dān)心，先直接往下看，第一個(gè)代碼（前序遍歷的遞歸思路）會(huì)幫助你提升感覺(jué)。

遞歸思路

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

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

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

前序遍歷

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

迭代思路

前序遍歷

我們需要一個(gè)棧來(lái)完成遍歷。

1.根節(jié)點(diǎn)入棧

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

3.重復(fù)2

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

Java：

來(lái)自官方題解

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

中序遍歷

還是使用一個(gè)棧來(lái)解決問(wèn)題。

步驟如下：

                    　1

　　　　　　　　　　/　  \

　　　　　　　　   2　　  3

　　　　　　     /   \　 /   \

　　　　　　　  4     5  6    7

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

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

總結(jié)：從根節(jié)點(diǎn)遍歷，先放入所有有左孩子的節(jié)點(diǎn)直到?jīng)]有，然后出棧，出棧的時(shí)候就將出棧的數(shù)字放入結(jié)果集，然后看其有沒(méi)有右孩子，有的話右孩子入棧。

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

后序遍歷

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

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

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]

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

莫里斯遍歷

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

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

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

聽(tīng)不懂沒(méi)關(guān)系，下面使用中序遍歷作為例子來(lái)理解莫里斯遍歷到底是什么意思，例子來(lái)自LeetCode官方題解：

中序遍歷

Step 1: 將當(dāng)前節(jié)點(diǎn)current初始化為根節(jié)點(diǎn)
Step 2: While current不為空，

若current沒(méi)有左子節(jié)點(diǎn)
   a. 將current添加到輸出
   b. 進(jìn)入右子樹(shù)，亦即, current = current.right
否則
   a. 在current的左子樹(shù)中，令current成為最右側(cè)節(jié)點(diǎn)的右子節(jié)點(diǎn)
   b. 進(jìn)入左子樹(shù)，亦即，current = current.left

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

     2
    / \
   4   5

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

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

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

前序遍歷

理解了中序遍歷，前序和后序遍歷相對(duì)來(lái)說(shuō)也就更容易理解了。所以前序和后序貼了思路，代碼我也沒(méi)自己寫(xiě)后submit，在這里就不放了。

算法的思路是從當(dāng)前節(jié)點(diǎn)向下訪問(wèn)先序遍歷的前驅(qū)節(jié)點(diǎn)，每個(gè)前驅(qū)節(jié)點(diǎn)都恰好被訪問(wèn)兩次。

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

后序遍歷

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

步驟：

當(dāng)前節(jié)點(diǎn)設(shè)置為臨時(shí)節(jié)點(diǎn)dump。

如果當(dāng)前節(jié)點(diǎn)的左孩子為空，則將其右孩子作為當(dāng)前節(jié)點(diǎn)。

如果當(dāng)前節(jié)點(diǎn)的左孩子不為空，在當(dāng)前節(jié)點(diǎn)的左子樹(shù)中找到當(dāng)前節(jié)點(diǎn)在中序遍歷下的前驅(qū)節(jié)點(diǎn)。

a) 如果前驅(qū)節(jié)點(diǎn)的右孩子為空，將它的右孩子設(shè)置為當(dāng)前節(jié)點(diǎn)。當(dāng)前節(jié)點(diǎn)更新為當(dāng)前節(jié)點(diǎn)的左孩子。

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

重復(fù)以上1、2直到當(dāng)前節(jié)點(diǎn)為空。

參考

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

【算法】二叉樹(shù)遍歷算法總結(jié)：前序中序后序遍歷

【算法】二叉樹(shù)遍歷算法總結(jié)：前序中序后序遍歷

前言

正文

二叉樹(shù)的定義

滿二叉樹(shù)

完全二叉樹(shù)（可以不滿）

二叉搜索樹(shù)

二叉樹(shù)前中后序遍歷

遍歷方法

題目介紹

前序遍歷

中序遍歷

后序遍歷

解題思路詳解與代碼實(shí)現(xiàn)

遞歸思路

前序遍歷

中序遍歷

后序遍歷

迭代思路

前序遍歷

中序遍歷

后序遍歷

莫里斯遍歷

中序遍歷

前序遍歷

后序遍歷

參考

相關(guān)閱讀更多精彩內(nèi)容

友情鏈接更多精彩內(nèi)容

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

【算法】二叉樹(shù)遍歷算法總結(jié)：前序中序后序遍歷

前言

正文

二叉樹(shù)的定義

滿二叉樹(shù)

完全二叉樹(shù)（可以不滿）

二叉搜索樹(shù)

二叉樹(shù)前中后序遍歷

遍歷方法

題目介紹

前序遍歷

中序遍歷

后序遍歷

解題思路詳解與代碼實(shí)現(xiàn)

遞歸思路

前序遍歷

中序遍歷

后序遍歷

迭代思路

前序遍歷

中序遍歷

后序遍歷

莫里斯遍歷

中序遍歷

前序遍歷

后序遍歷

參考

相關(guān)閱讀更多精彩內(nèi)容

友情鏈接更多精彩內(nèi)容

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