Very easy inorder DFS keeping tracking of previous element


  • 0
    A
    /**
     * Definition for a binary tree node.
     * struct TreeNode {
     *     int val;
     *     TreeNode *left;
     *     TreeNode *right;
     *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
     * };
     */
    class Solution {
        TreeNode *first = NULL;
        TreeNode *second = NULL;
        TreeNode *pre = NULL;
    public:
        void recoverTree(TreeNode* root) {
            DFS(root);
            
            if (first == NULL && second == NULL) return;
    
            int temp = first->val;
            first->val = second->val;
            second->val = temp;
        }
        
        void DFS(TreeNode *root) {
            if (root == NULL) return;
            
            DFS(root->left);
            
            if (pre != NULL) {
                if (root->val < pre->val) {
                    if (first == NULL) {
                        first = pre;
                        second = root;
                    } else {
                        second = root;
                    }
                }
            }
            
            pre = root;
            
            DFS(root->right);
            
        }
    };
    

  • 1
    J

    This is not O(1) space because if the tree's depth is N, recursive function calls use O(N) stack space in memory.


  • 1
    A

    @johnathan79717 Thanks, I didn't take that in the consideration. It is best case O(logn) and worst case O(n) space. Sorry for the confusion. But I still believe this is a good solution considering the fact no other space is used except the recursion stack memory.


  • 0

    johnathan is right, but I think this is acceptable in a interview, unless the interviewer is actually asking you for a Morris Traversal method or he test you the knowledge of Threading binary tree.

    Unless they are looking for an algorithm expert/senior roles or the interviewer intentionally want to deny you from an offer(Hate to admit this, but sometimes it does exists. If you don't like the interviewee, just blame it on the culture stuff. Think on the position of interviewee, you won't be comfortable if I ask you a ACM question in a interview), this solution is good enough for general interview purpose.


Log in to reply
 

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