Skip to content

114. 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:

img

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]

Solution:

方法一：头插法

采用头插法构建链表，也就是从节点 6 开始，在 6 的前面插入 5，在 5 的前面插入 4，依此类推。

为此，要按照 6→5→4→3→2→1 的顺序访问节点。如何遍历这棵树，才能实现这个顺序？

按照右子树 - 左子树 - 根的顺序 DFS 这棵树。

DFS 的同时，记录当前链表的头节点为 head。一开始 head 是空节点。

具体来说：

如果当前节点为空，返回。 递归右子树。 递归左子树。 把 root.left 置为空。 头插法，把 root 插在 head 的前面，也就是 root.right=head。 现在 root 是链表的头节点，把 head 更新为 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 {
    private TreeNode head;
    public void flatten(TreeNode root) {
        if (root == null){
            return;
        }

        flatten(root.right);
        flatten(root.left);

        root.left = null;
        root.right = head; // 头插法, 相当于链表的root.next = head
        head = root; // 现在链表头节点是 root
    }
}

复杂度分析

  • 时间复杂度：O(n)，其中 n 是二叉树的节点个数。
  • 空间复杂度：O(n)。递归需要 O(n) 的栈空间。

方法二：分治

方法一需要用到一个在 DFS 之外的变量 head，能否只在 DFS 中解决呢？

考虑分治，假如我们计算出了 root=1 左子树的链表 2→3→4，以及右子树的链表 5→6，那么接下来只需要穿针引线，把节点 1 和两条链表连起来：

先把 2→3→4 和 5→6 连起来，也就是左子树链表尾节点 4 的 right 更新为节点 5（即 root.right），得到 2→3→4→5→6。 然后把 1 和 2→3→4→5→6 连起来，也就是节点 1 的 right 更新为节点 2（即 root.left），得到 1→2→3→4→5→6。 最后把 root.left 置为空。 上面的过程，我们需要知道左子树链表的尾节点 4。所以 DFS 需要返回链表的尾节点。

链表合并完成后，返回合并后的链表的尾节点，也就是右子树链表的尾节点。如果右子树是空的，则返回左子树链表的尾节点。如果左右子树都是空的，返回当前节点。

/**
 * 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) {
        dfs(root);
    }

    private TreeNode dfs(TreeNode root){
        if (root == null){
            return null;
        }

        TreeNode leftTail = dfs(root.left);
        TreeNode rightTail = dfs(root.right);

        if (leftTail != null){
            leftTail.right = root.right; // 左边树链表 -> 右子树链表   
            root.right = root.left; // 当前节点 -> 左右子树合并后的链表
            root.left = null;
        }

        if (rightTail != null){
            return rightTail;
        }else if (leftTail != null){
            return leftTail;
        }else{
            return root;
        }
    }
}

// TC: O(n)
// SC: O(n)

/**
 * 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[] prev = new TreeNode[1];
        helper(root, prev);
        return;
    }

    private static void helper(TreeNode root, TreeNode[] prev){
        if (root == null){
            return;
        }

        TreeNode leftNode = root.left; // because leftChild can be changed
        TreeNode rightNode = root.right; 


        if (prev[0] != null){ //if: root is the 1st node to visit
            prev[0].right = root;
        }

        root.left = null; // OR = prev[0] if we need to make it a doubly linked list
        prev[0] = root;

        helper(leftNode, prev);
        helper(rightNode, prev);
    }
}
// TC: O(n)
// SC: O(n)