Task

Given a binary tree, return the inorder traversal of its nodes’ values.

Example

1
2
3
4
5
6
7
8

Input: [1,null,2,3]
   1
    \
     2
    /
   3

Output: [1,3,2]

Follow up: Recursive solution is trivial, could you do it iteratively?

Solution

递归实现

  • 时间复杂度：O(n)
  • 空间复杂度：O(最大高度)
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

// Runtime: 0 ms, faster than 100.00% of C++ online submissions for Binary Tree Inorder Traversal.
// Memory Usage: 8.6 MB, less than 26.04% of C++ online submissions for Binary Tree Inorder Traversal.
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    vector<int> inorderTraversal(TreeNode* root) {
        vector<int> ans;
        inorder(root,ans);
        return ans;
    }
private:
    void inorder(TreeNode *root,vector<int> &ans){
        if(!root) return;
        inorder(root->left,ans);
        ans.push_back(root->val);
        inorder(root->right,ans);
    }
};

非递归实现

  • 维护一个栈用于中序遍历，当前节点非空或栈非空时进行循环（每次循环遍历一个节点）：
    • 每次循环向左走到头，将路径上的节点依次压入栈中
    • 当栈中还有元素时，弹出栈顶元素，并将其值放入结果数组
    • 检查当前取到的栈顶元素是否有右子树（因为一定没有左子树），若有则继续沿着右子树遍历，没有则取栈的下一个元素
  • 时间复杂度：O(n)
  • 空间复杂度：栈深度取决于树的高度，O(最大高度)
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38

// Runtime: 4 ms, faster than 50.52% of C++ online submissions for Binary Tree Inorder Traversal.
// Memory Usage: 8.4 MB, less than 78.65% of C++ online submissions for Binary Tree Inorder Traversal.
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    vector<int> inorderTraversal(TreeNode* root) {
        //边界条件
        if(!root) return {};
        vector<int> ans;
        stack<TreeNode *> s;
        TreeNode *curr=root;
        //当前节点非空或栈非空时遍历，即有元素还未遍历到时就遍历
        while(curr || !s.empty()){
            //若当前节点非空，向左走到底
            while(curr){
                s.push(curr);
                curr=curr->left;
            }
            //取栈顶元素
            curr=s.top();
            ans.push_back(curr->val);
            s.pop();
            //检查当前节点是否有右子树，若有则进入右子树遍历
            curr=curr->right;
        }
        return ans;
    }
};