The list should be in non-decreasing order by construction. Iterate the list to find the node that is smaller than its previous node, then swap these two nodes.
Space complexity is O(n)
Solution 2 (Java)
/** * Definition of TreeNode: * public class TreeNode { * public int val; * public TreeNode left, right; * public TreeNode(int val) { * this.val = val; * this.left = this.right = null; * } * } */publicclassSolution {TreeNode first =null, second =null, prev =null; /** * @param root: the given tree * @return: the tree after swapping */publicTreeNodebstSwappedNode(TreeNode root) { prev =newTreeNode(Integer.MIN_VALUE);inorderTraversal(root);if (first !=null) {int temp =first.val;first.val=second.val;second.val= temp; }return root; }privatevoidinorderTraversal(TreeNode root) {if (root ==null)return;inorderTraversal(root.left);if (root.val<prev.val) {if (first ==null) first = prev; second = root; } prev = root;inorderTraversal(root.right); }}
Notes
We still use inorder traversal but modify it to check if we have any out-of-order nodes (the two nodes that are not in non-decreasing order).