Thinking process - in order traversal

https://discuss.leetcode.com/topic/3988/no-fancy-algorithm-just-simple-and-powerful-in-order-traversal/2

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    private TreeNode prevNode = null;
    private TreeNode swapNode1 = null;
    private TreeNode swapNode2 = null;
    public void recoverTree(TreeNode root) {
        //ArrayList<TreeNode> swappedNodes = new ArrayList<>();
        //in-order traversal
        dfsHelper(root);

        //swap two nodes

        int tmp = swapNode1.val;
        swapNode1.val = swapNode2.val;
        swapNode2.val = tmp;
    }

    private void dfsHelper(TreeNode root) {
        if (root == null) return ;

        dfsHelper(root.left);

        if (swapNode1 == null && prevNode != null && prevNode.val > root.val) {
            swapNode1 = prevNode;
        }

        if (swapNode1 != null && prevNode != null && prevNode.val > root.val) {
            swapNode2 = root;
        }

        prevNode = root;

        dfsHelper(root.right);
    }


}

Morris traversal

• using O(1) extra space to do in-order traversal

https://www.youtube.com/watch?v=wGXB9OWhPTg