解法

自己想的递归解法

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public void flatten(TreeNode root) {
        transferLinkedList(root);    
    }

    public TreeNode transferLinkedList(TreeNode root) {
        if (root == null) {
            return null;
        }
        // 左节点递归遍历转换为右指针链表
        TreeNode left = transferLinkedList(root.left);
        // 右节点递归遍历转换为右指针链表
        TreeNode right = transferLinkedList(root.right);
        root.left = null;
        if (left != null) {
            root.right = left;
            // 遍历到左节点链表的末尾
            while (left.right != null) {
                left = left.right;
            }
            // 左节点链表的末尾指向右节点链表的表头  
            left.right = right;
        } else {
            root.right = right;
        }
        return root;
    }
}

先序遍历迭代解法

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public void flatten(TreeNode root) {
        if (root == null) {
            return;
        }
        Stack<TreeNode> stack = new Stack<>();    
        TreeNode pre = null;
        // 先序遍历迭代写法
        stack.push(root);
        while (!stack.isEmpty()) {
            TreeNode node = stack.pop();
            // 前一个节点右指针指向当前节点
            if (pre != null) {
                pre.left = null;
                pre.right = node;
            }
            pre = node;
            if (node.right != null) {
                stack.push(node.right);
            }
            if (node.left != null) {
                stack.push(node.left);
            }
        }
    }
}

O（1）空间复杂度解法

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public void flatten(TreeNode root) {
        if (root == null) {
            return;
        }
        TreeNode cur = root;
        while (cur != null) {
            if (cur.left != null) {
                TreeNode left = cur.left;        
                TreeNode pre = left;
                while (pre.right != null) {
                    pre = pre.right;
                }
                pre.right = cur.right;
                cur.left = null;
                cur.right = left;
            }
            cur = cur.right;
        }
    }
}