二叉树的三种遍历方式（递归和非递归）

2020-12-14 04:53:37 编辑 1 阅读量:343

这里介绍一下二叉树的三种遍历方式：
- 前根序：根在前，也就是根→左→右的遍历
- 中根序：根在中，也就是左→根→右的遍历
- 后根序：根在后，也就是左→右根→的遍历

递归的方式遍历会更简单，代码如下：
```
class TreeNode(object):                                                                                                                                                                                          
    def __init__(self, x): 
        self.val = x 
        self.left = None
        self.right = None

class Solution(object):
    def preorderTraversal(self, root):
        """ 前根序遍历，这种遍历会更简单，因为跟节点一开始就遍历，就不必压栈
        :type root: TreeNode
        :rtype: List[int]
        """
        if not root:
            return []
        result = []
        stack = [root]
        while stack:
            node = stack.pop()
            result.append(node.val)
            if node.right:  # 右节点后出栈，所以要先压栈
                stack.append(node.right)
            if node.left:
                stack.append(node.left)
        return result

def preorder(self, root):
        """递归的前根序遍历"""
        def helper(n):
            if not n:
                return
            result.append(n.val)
            helper(n.left)
            helper(n.right)
        result = []
        helper(root)
        return result

def inorderTraversal2(self, root):
        """
        :type root: TreeNode
        :rtype: List[int]
        中根序非递归遍历，这种更好理解一些，但还是推荐下面的方式
        """
        if not root:
            return []
        stack = [root]
        used_stack = []    # 记录已经遍历过的节点，就是节点的值已经取出
        result = []
        while stack:
            node = stack.pop()
            # 右节点可能之前已经压栈，所以要判断一些是否在栈中,左节点无需判断
            if node.right and node.right not in stack and node.right not in used_stack:
                stack.append(node.right)
            # 判断是否遍历过
            if node.left and node.left not in used_stack:
                stack.append(node)    # 根节点继续压栈
                stack.append(node.left)
            else:
                result.append(node.val)
                used_stack.append(node)
        return result

def inorderTraversal(self, root):
        if not root:
            return []
        result = []
        stack = [(root, False)]    # 多加个值记录该节点是否已遍历
        while stack:
            node, is_visited = stack.pop()
            if not node:
                continue
            # 不管是根节点还是叶子节点都会被压栈2次
            if not is_visited:
                stack.append((node.right, False))
                stack.append((node, True))    # 已经遍历过一次根节点了
                stack.append((node.left, False))
            else:
                result.append(node.val)
        return result

def inorderTraversalByRecursive(self, root):
        def _inorder(n):
            if not n:
                return
            _inorder(n.left)
            result.append(n.val)
            _inorder(n.right)
        result = []
        _inorder(root)
        return result

def postorderTraversal(self, root):
        """ 
        :type root: TreeNode
        :rtype: List[int]
        如果理解了前面的inorderTraversal，那么这里也很好理解了
        """
        if not root:
            return []
        result = []
        stack = [(root, False)]
        while stack:
            root, is_visited = stack.pop()
            if not root:
                continue
            if not is_visited:
                stack.append((root, True))
                stack.append((root.right, False))
                stack.append((root.left, False))
            else:
                result.append(root.val)
        return result

def postorderTraversalByRecursive(self, root):
        def _postorder(n):
            if not n:
                return
            _postorder(n.left)
            _postorder(n.right)
            result.append(n.val)
        result = []
        _postorder(root)
        return result

if __name__ == "__main__":
    tree = TreeNode(1)
    tree.left = TreeNode(2)
    tree.right = TreeNode(3)
    tree.left.left = TreeNode(4)
    tree.left.right = TreeNode(5)
    s = Solution()
    print s.inorderTraversal(tree)
    print s.inorderTraversalByRecursive(tree)
```

二叉树的三种遍历方式（递归和非递归）

附件: