0114. Flatten Binary Tree to Linked List

---

Given the root of a binary tree, flatten the tree into a "linked list":

The "linked list" should use the same TreeNode class where the right child pointer points to the next node in the list and the left child pointer is always null. The "linked list" should be in the same order as a pre-order traversal of the binary tree.

Example 1:

Input: root = [1,2,5,3,4,null,6]
Output: [1,null,2,null,3,null,4,null,5,null,6]

Example 2:

Input: root = []
Output: []

Example 3:

Input: root = [0]
Output: [0]

Constraints:

• The number of nodes in the tree is in the range [0, 2000].
• -100 <= Node.val <= 100

---

解法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) {
        helper(root);
    }
    
    private TreeNode helper(TreeNode node){
        if(node == null)
            return null;
        
        if(node.left == null && node.right == null)
            return node;
        
        if(node.left == null)
            return helper(node.right);
        
        // 如果只有右节点为空
        if(node.right == null){
            
            // 把左节点放在右节点的位置
            node.right = node.left;
            // 把左节点清空
            node.left = null;
            // 返回下层的最右节点
            return helper(node.right);
        }
        
        // 如果左右节点都不为空, 将右节点暂时保存起来
        TreeNode right = node.right;
        // 左节点放到右节点的位置
        node.right = node.left;
        // 左节点清空
        node.left = null;
        // 得到右节点(原左节点)的下层最右节点, 把原来的右节点(暂时被保存起来)放在其右节点位置上
        helper(node.right).right = right;
        // 返回其下层的最右节点
        return helper(right);
    }
}

看网上其他的解法,有更简洁的写法.

class Solution {
    public void flatten(TreeNode root) {
        if (root == null) return;
        
        TreeNode left = root.left;
        TreeNode right = root.right;
        
        root.left = null;
        
        flatten(left);
        flatten(right);
        
        root.right = left;
        TreeNode cur = root;
        while (cur.right != null) cur = cur.right;
        cur.right = right;
    }
}