心之所向便是光

Leetcode 94.二叉树的中序遍历

  • 2021-06-22
  • 作者 Ender
  • 1.73K 字
  • 次阅读

题目描述：

给定一个二叉树的根节点 root ，返回它的 中序 遍历。

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

示例 1：

1
2
输入：root = [1,null,2,3]
输出：[1,3,2]

示例 2：

1
2
输入：root = []
输出：[]

示例 3：

1
2
输入：root = [1]
输出：[1]

示例 4：

1
2
输入：root = [1,2]
输出：[2,1]

示例 5：

1
2
输入：root = [1,null,2]
输出：[1,2]

提示：

  • 树中节点数目在范围 [0, 100] 内
  • -100 <= Node.val <= 100

链接：

https://leetcode-cn.com/problems/binary-tree-inorder-traversal

题目分析

1.递归解法

  非常容易想到的解法，也即按照 左子树-根结点-右子树 的顺序递归遍历二叉树即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
    void inorder(vector<int>& result, TreeNode* root){
        if(root){
            inorder(result, root->left);
            result.push_back(root->val);
            inorder(result, root->right);
        }
        return;
    }
public:
    vector<int> inorderTraversal(TreeNode* root) {
        vector<int> result;
        inorder(result, root);
        return result;
    }
};

  时间复杂度：$O(n)$，其中 $n$ 为二叉树的结点个数。我们遍历了一次二叉树。
  空间复杂度：$O(n)$，其中 $n$ 为二叉树的结点个数。也即栈的深度，而当二叉树是一条链时，最大深度为 $n$。

2.迭代解法

  其实我们需要做的就是将递归的栈显式地模拟出来。寻找左结点之前将根结点压栈，直到最左的结点，然后将栈顶出栈并加入到结果中，然后开始遍历右子树。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public:
    vector<int> inorderTraversal(TreeNode* root) {
        vector<int> result;
        stack<TreeNode*> s;
        while(root != nullptr || !s.empty()){
            while(root != nullptr){
                s.push(root);
                root = root->left;
            }
            root = s.top();
            result.push_back(root->val);
            s.pop();
            root = root->right;
        }
        return result;
    }
};

  时间复杂度：$O(n)$，其中 $n$ 为二叉树的结点个数。我们遍历了一次二叉树。
  空间复杂度：$O(n)$，其中 $n$ 为二叉树的结点个数。也即栈的大小。

本作品采用 知识共享署名-相同方式共享 4.0 国际许可协议 进行许可
, , , ,
最后编辑：2021-06-23