Simple and easy to understand C++ 48ms solution using DFS and O(1) space


  • 2
    H
    class Solution {
    public:
        TreeNode* pre; // 前一个访问节点
        TreeNode* first; // 交换元素的第一个
        TreeNode* second; // 交换元素的第二个
        
        void recoverTree(TreeNode* root) {
            if(root == NULL)    
                return ;
                
            pre = NULL;
            first = NULL;
            second = NULL;
            
            dfs(root);
            
            // 交换两个节点的值
            int tmp = first->val;
            first->val = second->val;
            second->val = tmp;
        }
        
        void dfs(TreeNode* root){
            if(root == NULL)
                return ;
                
            dfs(root->left);
            
            // 访问root节点
            if(pre != NULL && pre->val > root->val){
                if(first == NULL){ // 遇到第一个被调换的元素
                    first = pre;
                    second = root; // 如果两个调换的元素相邻,则应采用该设置
                }else{
                    // 遇到第二被调换的元素,此时两个元素不相邻
                    second = root;
                }
            }
            
            pre = root;
            
            dfs(root->right);
        }
    };

  • 8
    R

    There is implicit O(log N) space complexity of recursion. If the tree is unbalanced, that space complexity may even be O(N).


  • 0
    Y

    why is the space logn?


  • 0
    R

    Because recursive calls of dfs generate stack frames (space where variables of a function reside in memory). And there is going to be "height of the tree" of those calls made simultaneously at the bottom of recursion. If the tree is balanced, then its height is O(log(n)).


  • 0

    cool~~~~~~~~~~~~


  • 0

    one more tip can make the solution better:
    if you have found both of the nodes, the traverse could stop.


  • 0
    B

    Obviously, It's not O(1) space because of recursion.
    You need to use Mirros Traversal to archive O(1) space complexity.


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.