Simple iterative way with explanation


  • 0
    Y

    there are 2 cases need to be taken care. In order traverse is the easiest way.

    1. The swapped nodes are next to each other.
      for example: 1 2 3 4 5 6 7 -> 1 3 2 4 5 6 7
    2. The swapped nodes are not next to each other
      for example: 1 2 3 4 5 6 7 -> 1 6 3 4 5 2 7
      The first error node is always larger than the next one. Number 3 in the first case and Number 6 in the second case.
      The second error node is always the one who is less than previous. Number 2 in first case and Number 2 in the second case.

    So we just use the iterative way to traverse the tree. when find the first number smaller than previous node, set it to err1 to the previous node and at mean time set the err2 as the current node.

    If it is the case 2, the err2 will be set again. otherwise it will be case 1.

    Stack<TreeNode> map = new Stack<TreeNode>();
                TreeNode pre = new TreeNode(int.MinValue);
                if (root == null)
                    return;
                TreeNode err1 = null;
    			TreeNode err2 = null;
                for (TreeNode i = root; i != null; i = i.left)
                {
                    map.Push(i);
                }
    
                while (map.Count != 0)
                {
                    TreeNode temp = map.Pop();
                    if (temp.val < pre.val)
                    {
                        if (err1 == null)
                        {
                            err1 = pre;
                        }
                      	err2 = temp;
                    }
    				pre = temp;
                    temp = temp.right;
    
                    for (TreeNode i = temp; i != null; i = i.left)
                    {
                        map.Push(i);
                    }
                }
    
                int t2 = err2.val;
                err2.val = err1.val;
                err1.val = t2;

Log in to reply
 

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