leetcode-二叉树的前序、中序、后序、层序的递归和非递归实现

电玩女神 2023-06-18 13:56 23阅读 0赞

### 文章目录 ###

*   *  1. 二叉树的遍历
     *  2. 前序遍历
     *   *  2.1. 递归实现
         *  2.2. 非递归实现
     *  3. 中序遍历
     *   *  3.1. 递归实现
         *  3.2. 非递归实现
     *  4. 后序遍历
     *   *  4.1. 递归实现
         *  4.2. 非递归实现
     *  5. 层序遍历

## 1. 二叉树的遍历 ##

面试中，尤其是校招面试中（哈哈，社招面试估计是嫌这种题目太简单，不屑于考察），经常被问到的一个题目就是二叉树的各种遍历算法，而我们常见的二叉树的遍历方式有前序遍历、中序遍历、后序遍历、层序遍历，所谓的前序/中序/后序是指遍历**根节点**的顺序，而层序遍历则是按照二叉树的深度方向来遍历，对应的遍历节点的顺序如下：

1.  前序遍历：最先遍历跟节点。遍历顺序为 根节点->左子树->右子树；
2.  中序遍历：中间遍历根节点。遍历顺序为 左子树->根节点->右子树；
3.  后序遍历：最后遍历根节点。遍历顺序为 左子树->右子树->根节点；
4.  层序遍历：从二叉树的第一层根节点开始遍历，然后第二层从最左往右遍历，再是第三层从最左往右遍历。。。

## 2. 前序遍历 ##

题目链接：https://leetcode.com/problems/binary-tree-preorder-traversal

### 2.1. 递归实现 ###

下面代码中的`res`是全局变量。

def binary_tree_pre_order_traversal(root, res):
        if root:
            res.append(root.val)
            binary_tree_pre_order_traversal1(root.left, res)
            binary_tree_pre_order_traversal1(root.right, res)

### 2.2. 非递归实现 ###

使用栈来保存树中的节点，我们以列数据结构来实现栈。

def binary_tree_pre_order_traversal(root):
        res = []
        s = []
        if root:
            s.append(root)
        while s:
            root = s.pop()
            res.append(root.val)
            if root.right:
                s.append(root.right)
            if root.left:
                s.append(root.left)
    
        return res

## 3. 中序遍历 ##

题目链接：https://leetcode.com/problems/binary-tree-inorder-traversal

### 3.1. 递归实现 ###

下面代码中的`res`是全局变量。

def tree_in_order_traversal(root, res):
        if root:
            tree_in_order_traversal1(root.left, res)
            res.append(root.val)
            tree_in_order_traversal1(root.right, res)

### 3.2. 非递归实现 ###

def tree_in_order_traversal(root):
        res = []
        s = []
        while root or s:
            while root:
                s.append(root)
                root = root.left
            root = s.pop()
            res.append(root.val)
            root = root.right
        return res

## 4. 后序遍历 ##

### 4.1. 递归实现 ###

下面代码中的`res`是全局变量。

def binary_tree_post_order_traversal1(root, res):
        if root:
            binary_tree_post_order_traversal1(root.left, res)
            binary_tree_post_order_traversal1(root.right, res)
            res.append(root.val)

### 4.2. 非递归实现 ###

二叉树的后续遍历的非递归实现方式之所以难度比前序遍历、中序遍历要高（哈哈，不是我说的哈，是leetcode说的，leetcode给后序遍历的难度tag是hard，而前序遍历、中序遍历的难度tag都是medium），是因为后序遍历是最后才遍历根节点，而我们通常的方式是要从上往下遍历，所以必然会经过根节点，所以必须要保存下来根节点，也必然要先遍历左节点，所以也要保存下来，因此步骤就会比前序遍历和中序遍历更多一些，具体代码如下：

def binary_tree_post_order_traversal2(root):
        res = []
        s =[]
        while root or s:
            while root:
                s.append(root)
                if root.left:
                    root = root.left
                else:
                    root = root.right
            root = s.pop()
            res.append(root.val)
            if len(s) > 0 and s[-1].left == root:
                root = s[-1].right
            else:
                root = None
        return res

## 5. 层序遍历 ##

题目链接：https://leetcode.com/problems/binary-tree-level-order-traversal

def binary_tree_level_order_traversal(root):
        if not root:
            return []
        res = [[root.val]]
        d = deque([root])
    
        while d:
            tmp_val = []
            for _ in range(0, len(d)):
                tmp_node = d.popleft()
                if tmp_node.left:
                    d.append(tmp_node.left)
                    tmp_val.append(tmp_node.left.val)
                if tmp_node.right:
                    d.append(tmp_node.right)
                    tmp_val.append(tmp_node.right.val)
            if tmp_val:
                res.append(tmp_val)
    
        return res