94_BinaryTreeInorderTraversal

---

title: 94. Binary Tree Inorder Traversal tags: - backtracking - stack categories: leetcode comments: false

problem

solution

option 1 - dfs

class Solution {
public:
    void inorder(TreeNode* root, vector<int>& ret){
        if(!root) return;
        inorder(root->left, ret);
        ret.push_back(root->val);
        inorder(root->right, ret);
        
    }
    vector<int> inorderTraversal(TreeNode* root) {
        vector<int> ret;
        inorder(root, ret);
        return ret;
    }
};

option 2 - iterative + stack

class Solution {
public:
    vector<int> inorderTraversal(TreeNode* root) {
        stack<TreeNode*> sta;
        TreeNode *p = root;
        vector<int> ret;
        while (p || !sta.empty()) {
            while (p) { // L
                sta.push(p);
                p=p->left; 
            }
            p = sta.top();
            sta.pop();
            ret.push_back(p->val);  // V
            p = p->right;   // R
            
            
        }
        return ret;
    }
};

analysis

• option 1 - dfs
  • 時間複雜度：O(n)，其中 n 是二叉樹的節點數量。每個節點都會被訪問一次。
  • 空間複雜度：O(h)，其中 h 是二叉樹的高度。遞歸的呼叫堆疊的深度取決於樹的高度。
• option 2 - iterative + stack
  • 時間複雜度：O(n)，其中 n 是二叉樹的節點數量。每個節點都會被訪問一次。
  • 空間複雜度：O(h)，其中 h 是二叉樹的高度。堆疊的最大大小取決於樹的高度，最壞情況下為 O(n)（當樹為單鏈時）