Blog Content

python实现二叉树的前中后序遍历

Python 算法   2011-02-02 21:24:10

---

二叉树的遍历分深度优先遍历（DFS）和宽度优先遍历（BFS）。其中深度优先遍历又分为先序遍历，中序遍历，后序遍历。因为二叉树是递归类数据结构，因此大部分关于二叉树的操作都可以通过递归实现。

先定义二叉树类：

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

 遍历顺序：

前序遍历： root-left-right，根节点——左子节点——右子节点；

中序遍历： left-root-right，左子节点——根节点——右子节点；

后序遍历： left-right-root，左子节点——右子节点——根节点；

递归方法：

def traverse(root, order_type="preorder"):
    if not root:
        return 
    if order_type=="preorder":
        print(root.val)
    traverse(root.left)
    if order_type=="inorder":
        print(root.val)
    traverse(root.right) 
    if order_type=="postorder":
        print(root.val)

层次遍历：

def BFS(root):
    queue = [root]
    while queue:
        n = len(queue)
        for i in range(n):
            q = queue.pop(0)
            if q:
                print(q.val)
                queue.append(q.left if q.left else None)
                queue.append(q.right if q.right else None)

二叉树的最大深度

当前树的最大深度等于（1+max(左子树最大深度，右子树最大深度)）。

def maxDepth(root):
    if not root:
        return 0
    return 1+max(maxDepth(root.left),maxDepth(root.right))

二叉树的最小深度

最小深度是从根节点到最近叶子节点的最短路径上的节点数量。可以通过递归求左右节点的最小深度的较小值，也可以层序遍历找到第一个叶子节点所在的层数。

class Solution:
    def minDepth(self, root: TreeNode) -> int:
        if not root:
            return 0
        if not root.left and not root.right:
            return 1 
        if not root.right:
            return 1+self.minDepth(root.left)
        if not root.left:
            return 1+self.minDepth(root.right)
        return 1+min(self.minDepth(root.left),self.minDepth(root.right))

二叉树的所有路径

根节点到叶子节点的所有路径。

def traverse(node):
    if not node.left and not node.right:
        return [str(node.val)]
    left, right = [], []
    if node.left:
        left = [str(node.val) + x for x in traverse(node.left)]
    if node.right:
        right = [str(node.val) + x for x in traverse(node.right)]

    return left + right

---

上一篇：二叉树各种计算公式总结
下一篇：约瑟夫环，报数出列