Thinking process I - Divide and Conquer

Use a helper function and set its return value to the last node

get the last node from left or from right

Mistakes

1. Pay attention to the replace order
2. don't forget to set left node to null

public class Solution {
    public void flatten(TreeNode root) {
        dfsHelper(root);
    }

    //move left to right and return lastNode
    private TreeNode dfsHelper(TreeNode root) {
        if (root == null) {
            return null;
        }

        if (root.left == null && root.right == null) {
            return root;
        }

        TreeNode leftLastNode = dfsHelper(root.left);
        TreeNode rightLastNode = dfsHelper(root.right);

        if (leftLastNode != null) {
            leftLastNode.right = root.right;
            root.right = root.left;
            root.left = null;
        }

        return rightLastNode != null ? rightLastNode : leftLastNode;
    }
}