LeetCode题目（Python实现）：二叉树的中序遍历

一时失言乱红尘 2023-07-15 02:47 78阅读 0赞

### 文章目录 ###

*  题目
 *   *  想法一：递归
     *   *  算法实现
         *  执行结果
         *  复杂度分析
     *  迭代
     *   *  算法实现
         *  执行结果
         *  复杂度分析
     *  颜色标记法
     *   *  算法实现
         *  执行结果
         *  复杂度分析
     *  小结

# 题目 #

给定一个二叉树，返回它的*中序* 遍历。

输入: [1,null,2,3]
       1
        \
         2
        /
       3
    
    输出: [1,3,2]

**进阶**: 递归算法很简单，你可以通过迭代算法完成吗？

## 想法一：递归 ##

### 算法实现 ###

def inorderTraversal(self, root: TreeNode) -> List[int]:
        if not root:
            return []
        return self.inorderTraversal(root.left) + [root.val] + self.inorderTraversal(root.right)

### 执行结果 ###

**执行结果** : 通过  
**执行用时** : 28 ms, 在所有 Python3 提交中击败了92.47%的用户  
**内存消耗** : 13.6 MB, 在所有 Python3 提交中击败了5.02%的用户  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ1NTU2NTk5_size_16_color_FFFFFF_t_70]

### 复杂度分析 ###

*  时间复杂度：O(n)
 *  空间复杂度：O(n)

## 迭代 ##

### 算法实现 ###

def inorderTraversal(self, root: TreeNode) -> List[int]:
        res = []
        stack = []
        while stack or root:
            # 不断往左子树方向走，每走一次就将当前节点保存到栈中
            # 这是模拟递归的调用
            if root:
                stack.append(root)
                root = root.left
            # 当前节点为空，说明左边走到头了，从栈中弹出节点并保存
            # 然后转向右边节点，继续上面整个过程
            else:
                tmp = stack.pop()
                res.append(tmp.val)
                root = tmp.right
        return res

### 执行结果 ###

![在这里插入图片描述][20200315022801801.png]

### 复杂度分析 ###

*  时间复杂度：O(n)
 *  空间复杂度：O(n)

## 颜色标记法 ##

### 算法实现 ###

def inorderTraversal(self, root: TreeNode) -> List[int]:
        WHITE, GRAY = 0, 1
        res = []
        stack = [(WHITE, root)]
        while stack:
            color, node = stack.pop()
            if node is None:
                continue
            if color == WHITE:
                stack.append((WHITE, node.right))
                stack.append((GRAY, node))
                stack.append((WHITE, node.left))
            else:
                res.append(node.val)
        return res

### 执行结果 ###

![在这里插入图片描述][20200315024120265.png]

### 复杂度分析 ###

*  时间复杂度：O(n)
 *  空间复杂度：O(n)

## 小结 ##

中序遍历在用递归时，没想到真的很简单，但是迭代却想了很久没有得出结果，最后看了题解，用的也是栈，但是在转换节点上用了一个巧妙的方法，即在root为空时，弹出一个节点并输出答案，然后root变为其右节点。

这种方法可以说是巧妙的应用了二叉树和栈结合的特性，学到了学到了。。。下次遇到二叉树可能会想到这种方法=。=

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ1NTU2NTk5_size_16_color_FFFFFF_t_70]: /images/20230529/644e9619cf0c4294844422ec0670d781.png
[20200315022801801.png]: /images/20230529/8db0e616cc11488d997f52e2f4e403a7.png
[20200315024120265.png]: /images/20230529/3cbc0138a6774ea59ce4df0d9927ca5b.png