Iterative, simple


  • 0
    V
    public void RecoverBinarySearchTree(TreeNode root) {       
           var t = root;
            TreeNode firstNode = null, secondNode = null, prev = null;
    
            var s = new Stack<TreeNode>();
            while (t != null || s.Count > 0) {
                if (t != null) {
                    s.Push(t);
                    t = t.left;
                } else {
                    t = s.Pop();
                    if (prev == null) {
                        prev = t;
                    } else {
                        if (prev.val > t.val) {
                            if (firstNode == null) {
                                firstNode = prev; //found firstNode. For now save t as second node
                                secondNode = t;
                            } else {
                                secondNode = t;
                            }
                        }
                    }
                    prev = t; //update prev
                    t = t.right; //move on
                }
            }
    
            Swap(firstNode, secondNode); //finally swap
    }
    

Log in to reply
 

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