二叉树遍历

by · 2018年11月17日 · 859 Words · ~2min reading time | Improve on


原文链接： 二叉树遍历

二叉树是一种非常重要的数据结构，很多其它数据结构都是基于二叉树的基础演变而来的。对于二叉树，有深度遍历和广度遍历，
深度遍历有前序、中序以及后序三种遍历方法，广度遍历即我们平常所说的层次遍历。
因为树的定义本身就是递归定义，因此采用递归的方法去实现树的三种遍历不仅容易理解而且代码很简洁，而对于广度遍历来说，需要其他数据结构的支撑，比如堆了。所以，对于一段代码来说，可读性有时候要比代码本身的效率要重要的多。

四种主要的遍历思想为：

深度遍历 前序遍历：根结点 ---> 左子树 ---> 右子树
深度遍历 中序遍历：左子树---> 根结点 ---> 右子树
深度遍历 后序遍历：左子树 ---> 右子树 ---> 根结点
广度遍历 层次遍历：只需按层次遍历即可

前序遍历：1 2 4 5 7 8 3 6
中序遍历：4 2 7 5 8 1 3 6
后序遍历：4 7 8 5 2 6 3 1
层次遍历：1 2 3 4 5 6 7 8

只要了解了先序遍历，中序和后序遍历都懂了。
这里面用到了栈，用栈不断压入根、左孩子，通过pop来回溯父节点，再访问右孩子。

先序遍历

"""
Definition of TreeNode:
class TreeNode:
    def __init__(self, val):
        self.val = val
        self.left, self.right = None, None
"""

class Solution:
    """
    @param root: The root of binary tree.
    @return: Postorder in ArrayList which contains node values.
    """
    result = []
    def preorderTraversal(self, root):
        # write your code here
        if root is None:
            return []
        stack = []
        seq = [] #记录先序访问序列
        output = []
        while ((root!=None) | (len(stack)!=0)):
            if root!=None:
                seq.append(root.val)   #先访问根节点
                stack.append(root)  
                root = root.left   
            else:
                root = stack.pop() #回溯至父节点
                root = root.right
        return seq

中序遍历

"""
Definition of TreeNode:
class TreeNode:
    def __init__(self, val):
        self.val = val
        self.left, self.right = None, None
"""

class Solution:
    """
    @param root: The root of binary tree.
    @return: Postorder in ArrayList which contains node values.
    """
    result = []
    def inorderTraversal(self, root):
        # write your code here
        if root is None:
            return []
        stack = []
        seq = []
        output = []
        while ((root!=None) | (len(stack)!=0)):
            if root!=None:
                stack.append(root)
                root = root.left
            else:
                root = stack.pop()
                seq.append(root.val) # 左孩子先pop出来，再pop根节点
                root = root.right
         
        return seq

后序遍历

先序：根左右
后续：左右根

即把先序顺序中的 ‘根左右’转换为‘根右左’，然后反过来就变成了‘左右根’。

"""
Definition of TreeNode:
class TreeNode:
    def __init__(self, val):
        self.val = val
        self.left, self.right = None, None
"""

class Solution:
    """
    @param root: The root of binary tree.
    @return: Postorder in ArrayList which contains node values.
    """
    result = []
    def postorderTraversal(self, root):
        # write your code here
        if root is None:
            return []
        stack = []
        seq = []
        output = []
        while ((root!=None) | (len(stack)!=0)):
            if root!=None:
                seq.append(root.val)
                stack.append(root)
                root = root.right  # 这从left变成了 right
            else:
                root = stack.pop()
                root = root.left # 这从right变成了 left
                
        while seq:  # 后序遍历 是 将先序遍历的反过来
            output.append(seq.pop())

        return output

作者：fighting41love
链接：https://www.jianshu.com/p/7cbb17fe525c

Tags:

`