Reading

树的遍历

Apr 25, 2024
30734 views
Algorithm
#Algorithm

二叉树结构

class TreeNode:
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None

递归

时间复杂度：\(O(n)\)，\(n\)为节点数，访问每个节点恰好一次。
空间复杂度：空间复杂度：\(O(h)\)，\(h\)为树的高度。最坏情况下需要空间\(O(n)\)，平均情况为\(O(logn)\)

递归1: 二叉树遍历最易理解和实现版本

class Solution:
    def preorderTraversal(self, root: TreeNode) -> List[int]:
        if not root:
            return []
        # 前序递归
        return [root.val] + self.preorderTraversal(root.left) + self.preorderTraversal(root.right)
        # # 中序递归
        # return self.inorderTraversal(root.left) + [root.val] + self.inorderTraversal(root.right)
        # # 后序递归
        # return self.postorderTraversal(root.left) + self.postorderTraversal(root.right) + [root.val]

递归2: 通用模板

可以适应不同的题目，添加参数、增加返回条件、修改进入递归条件、自定义返回值

class Solution:
    def preorderTraversal(self, root: TreeNode) -> List[int]:
        def dfs(cur):
            if not cur:
                return
                # 前序递归
            res.append(cur.val)
            dfs(cur.left)
            dfs(cur.right)
            # 中序递归
            # dfs(cur.left)
            # res.append(cur.val)
            # dfs(cur.right)
            # # 后序递归
            # dfs(cur.left)
            # dfs(cur.right)
            # res.append(cur.val)

        res = []
        dfs(root)
        return res

迭代

时间复杂度：\(O(n)\)，\(n\)为节点数，访问每个节点恰好一次。

空间复杂度：\(O(h)\)，\(h\)为树的高度。取决于树的结构，最坏情况存储整棵树，即\(O(n)\)

迭代1: 前序遍历最常用模板（后序同样可以用）

class Solution:
    def preorderTraversal(self, root: TreeNode) -> List[int]:
        if not root:
            return []
        res = []
        stack = [root]
        # 前序迭代模板：最常用的二叉树DFS迭代遍历模板
        while stack:
            cur = stack.pop()
            res.append(cur.val)
            if cur.right:
                stack.append(cur.right)
            if cur.left:
                stack.append(cur.left)
        return res

# # 后序迭代，相同模板：将前序迭代进栈顺序稍作修改，最后得到的结果反转
        # while stack:
        #     cur = stack.pop()
        #     res.append(cur.val)
        #     if cur.left:
        #         stack.append(cur.left)
        #     if cur.right:
        #         stack.append(cur.right)
        # return res[::-1]

迭代2: 前、中、后序遍历通用模板（只需一个栈的空间）

class Solution:
    def inorderTraversal(self, root: TreeNode) -> List[int]:
        res = []
        stack = []
        cur = root
        # 中序，模板：先用指针找到每颗子树的最左下角，然后进行进出栈操作
        while stack or cur:
            while cur:
                stack.append(cur)
                cur = cur.left
            cur = stack.pop()
            res.append(cur.val)
            cur = cur.right
        return res

        # # 前序，相同模板
        # while stack or cur:
        #     while cur:
        #         res.append(cur.val)
        #         stack.append(cur)
        #         cur = cur.left
        #     cur = stack.pop()
        #     cur = cur.right
        # return res

        # # 后序，相同模板
        # while stack or cur:
        #     while cur:
        #         res.append(cur.val)
        #         stack.append(cur)
        #         cur = cur.right
        #     cur = stack.pop()
        #     cur = cur.left
        # return res[::-1]

迭代3：标记法迭代（需要双倍的空间来存储访问状态）

前、中、后、层序通用模板，只需改变进栈顺序或即可实现前后中序遍历，
而层序遍历则使用队列先进先出。0表示当前未访问，1表示已访问。

class Solution:
    def preorderTraversal(self, root: TreeNode) -> List[int]:
        res = []
        stack = [(0, root)]
        while stack:
            flag, cur = stack.pop()
            if not cur: continue
            if flag == 0:
                # 前序，标记法
                stack.append((0, cur.right))
                stack.append((0, cur.left))
                stack.append((1, cur))

                # # 后序，标记法
                # stack.append((1, cur))
                # stack.append((0, cur.right))
                # stack.append((0, cur.left))

                # # 中序，标记法
                # stack.append((0, cur.right))
                # stack.append((1, cur))
                # stack.append((0, cur.left))
            else:
                res.append(cur.val)
        return res

        # # 层序，标记法
        # res = []
        # queue = [(0, root)]
        # while queue:
        #     flag, cur = queue.pop(0)  # 注意是队列，先进先出
        #     if not cur: continue
        #     if flag == 0:
        # 层序遍历这三个的顺序无所谓，因为是队列，只弹出队首元素
        #         queue.append((1, cur))
        #         queue.append((0, cur.left))
        #         queue.append((0, cur.right))
        #     else:
        #         res.append(cur.val)
        # return res

层序遍历

class Solution:
    def levelOrder(self, root: TreeNode) -> List[List[int]]:
        if not root:
            return []
        cur, res = [root], []
        while cur:
            lay, layval = [], []
            for node in cur:
                layval.append(node.val)
                if node.left: lay.append(node.left)
                if node.right: lay.append(node.right)
            cur = lay
            res.append(layval)
        return res

莫里斯遍历

时间复杂度：\(O(n)\)，\(n\)为节点数，看似超过\(O(n)\)，有的节点可能要访问两次，实际分析还是\(O(n)\)，
空间复杂度：\(O(1)\)，如果在遍历过程中就输出节点值，则只需常数空间就能得到中序遍历结果，空间只需两个指针。
如果将结果储存最后输出，则空间复杂度还是\(O(n)\)。

PS：莫里斯遍历实际上是在原有二叉树的结构基础上，构造了线索二叉树，

线索二叉树定义为：原本为空的右子节点指向了中序遍历顺序之后的那个节点，把所有原本为空的左子节点都指向了中序遍历之前的那个节点

此处只给出中序遍历，前序遍历只需修改输出顺序即可
而后序遍历，由于遍历是从根开始的，而线索二叉树是将为空的左右子节点连接到相应的顺序上，使其能够按照相应准则输出
但是后序遍历的根节点却已经没有额外的空间来标记自己下一个应该访问的节点，
所以这里需要建立一个临时节点dump，令其左孩子是root。并且还需要一个子过程，就是倒序输出某两个节点之间路径上的各个节点。

莫里斯遍历，借助线索二叉树中序遍历（附前序遍历）

class Solution:
    def inorderTraversal(self, root: TreeNode) -> List[int]:
        res = []
        # cur = pre = TreeNode(None)
        cur = root

        while cur:
            if not cur.left:
                res.append(cur.val)
                # print(cur.val)
                cur = cur.right
            else:
                pre = cur.left
                while pre.right and pre.right != cur:
                    pre = pre.right
                if not pre.right:
                    # print(cur.val) 这里是前序遍历的代码，前序与中序的唯一差别，只是输出顺序不同
                    pre.right = cur
                    cur = cur.left
                else:
                    pre.right = None
                    res.append(cur.val)
                    # print(cur.val)
                    cur = cur.right
        return res

N叉树遍历

时间复杂度：时间复杂度：O(M)，其中 M 是 N 叉树中的节点个数。每个节点只会入栈和出栈各一次。
空间复杂度：O(M)。在最坏的情况下，这棵 N 叉树只有 2 层，所有第 2 层的节点都是根节点的孩子。
将根节点推出栈后，需要将这些节点都放入栈，共有 M−1个节点，因此栈的大小为 O(M)。

# Definition for a Node.
class Node:
    def __init__(self, val=None, children=None):
        self.val = val
        self.children = children

N叉树简洁递归

class Solution:
    def preorder(self, root: 'Node') -> List[int]:
        if not root: return []
        res = [root.val]
        for node in root.children:
            res.extend(self.preorder(node))
        return res

N叉树通用递归模板

class Solution:
    def preorder(self, root: 'Node') -> List[int]:
        res = []

        def helper(root):
            if not root:
                return
            res.append(root.val)
            for child in root.children:
                helper(child)

        helper(root)
        return res

N叉树迭代方法

class Solution:
    def preorder(self, root: 'Node') -> List[int]:
        if not root:
            return []
        s = [root]
        # s.append(root)
        res = []
        while s:
            node = s.pop()
            res.append(node.val)
            # for child in node.children[::-1]:
            #     s.append(child)
            s.extend(node.children[::-1])
        return res

先序遍历和后序遍历为什么不能唯一地确定一棵树？

根据一棵树的先序遍历和中序遍历，或者后序遍历和中序遍历序列，都可以唯一地确定一棵树。

树中的节点，分为度为0，1，2的结点。如果树中只有一个节点，那么可以唯一确定一棵树，即只有一个节点的树。

当树中结点个数大于等于2的情况，树中的叶子结点和它的父亲结点中，至少有一种存在如下的情况。（为方便起见，我们先从叶子节点入手）

case 1:                             case2:                      case 3:

A                                    D                                   F

/     \                                 /                                        \

B       C                            E                                          G

即，叶子结点的父亲有两个孩子，只有左孩子，只有右孩子的情况。我们只需要证明，如果树存在这三种结构中的哪一种，可以唯一确定一棵树，什么情况下又不能唯一确定一棵树呢?

  1. case 1:

A

/     \

B       C

前序遍历: ABC， 后序遍历： BCA

现在，我们根据遍历序列，看看能否得到另一种树的结构？

由于在前序遍历中A第一个出现，则A为这棵树的根节点。（前： A  BC        后： BC　A）

接下来，我们看，BC可以只在A的左子树或者右子树中出现吗？

如果BC只出现在树的左子树或者右子树中，则根据前序遍历， B应为子树的树，C为B的孩子。则后序遍历时，C应在B的前面。但实际的后序遍历，C在B的后面。因此，BC不可能只出现在A的左子树或者右子树当中。因此，在这种情况下，可以唯一确定树的结构。

  1. case 2:

D

/

E

前序遍历： DE, 后序遍历： ED

则下面树的结构也满足前序和后序遍历的序列。

D

\

E

即这种情况，不能唯一确定一棵树。

  1. case 3:

同case 2情况相似，也不能唯一确定一棵树。

我们可以把叶子结点推广成一棵树的情况，即如果树中只存在度为0和度为2的节点，则根据它的前序遍历和后序遍历序列，可以重构树的结构。否则不能唯一重构树。那如果给你一个前序和后序遍历的序列，我们如何来判断，它是否可以唯一地构造一棵树呢？

即我们根据遍历序列，来看看树中，如果所有结点的度为0或者2，则可以唯一还原。

例： 前序： ABDFGEC  后序： FGDEBCA

第一步： 根结点为A

第二步： 根据前后序序列，B为A的左子树的根，根据后序序列 将整个序列分为两部分： FGDEB， C 即A有两个孩子。

第三步： 继续看以B为树的树，前序为 BDFGE, 后序： FGDEB 。 按照分析A的方法来分析 B，最后得知，这棵树可以唯一确定。

但是如果把上面序列中的结点C给去掉，即：前序： ABDFGE  后序： FGDEBA， 此时就不能唯一确定了。