94. Binary Tree Inorder Traversal - cocoder39/coco39_LC GitHub Wiki

94. Binary Tree Inorder Traversal

2020 Notes:

class Solution:
    def inorderTraversal(self, root: TreeNode) -> List[int]:
        stack = []
        cur = root
        res = []
        
        while cur or stack :
            while cur:
                stack.append(cur)
                cur = cur.left
            
            cur = stack.pop()
            res.append(cur.val)
            cur = cur.right
    
        return res

======================================================================

use stack to mimic call stack of recursion, time complexity is O(n) and space complexity is O(n)

vector<int> inorderTraversal(TreeNode* root) {
        vector<int> res;
        stack<TreeNode*> s;
        while (root || ! s.empty()) {
            if (root) {
                s.push(root);
                root = root->left;
            }
            else { // ! root && ! S.empty()
                TreeNode* node = s.top();
                s.pop();
                res.push_back(node->val);
                root = node->right; 
            }
        }
        return res;
    }

morris traversal, time complexity is O(n) and space complexity is O(1). the confused part of time complexity is

while (pre->right && pre->right != cur) { 
                    pre = pre->right; //right most child of left subtree is pre
}

is that O(n * h) where h is height ? Nope, each check would go left first, then all the way right. there are n - 1 edges for a n-node-tree, each edge would only be visited twice (one for building thread, the other for deleting thread), then time complexity is still O(n).

vector<int> inorderTraversal(TreeNode* root) {
        vector<int> res;
        TreeNode* cur = root;
        while (cur) {
            if (cur->left) { 
                TreeNode* pre = cur->left;
                while (pre->right && pre->right != cur) { 
                    pre = pre->right; //right most child of left subtree is pre
                }
                if (! pre->right) {//first time found pre, do not visit cur, just build its pre thread
                    pre->right = cur; //thread make successor as right subtree, move right only if done with left 
                    cur = cur->left; 
                }
                else { //pre->right == cur, pre thread is already built, its left has been visited, now visit it and move right
                    pre->right = nullptr;
                    res.push_back(cur->val);
                    cur = cur->right;
                }
            }
            else { //(! cur->left)  
                res.push_back(cur->val); //visit cur and cur->right only if left has been visited
                cur = cur->right;
            }
        }
        return res;
    }
⚠️ **GitHub.com Fallback** ⚠️