114. Flatten Binary Tree to Linked List

Leetcode link

题目简介

/**
 * @param {TreeNode} root
 * @return {void} Do not return anything, modify root in-place instead.
 */

题目给我们一个二叉树的根节点 root

要求我们在原地把树改成链表，链表以 node.right 指针连接，链表连接顺序为树的前序遍历顺序

解题思路

前序遍历的顺序是：根节点 -> 左子树 -> 右子树

假设我们有一棵树：

     1
    / \
   2   5
  / \   \
 3   4   6

前序遍历的顺序是：1, 2, 3, 4, 5, 6

我们的移动顺序如下所示：

1. 找到根节点的第一个左子节点 leftChild（就是上面例子的 2）
2. 判断 leftChild 是否有右子节点，如果有则进入第 3 步，否则跳到第 6 步
3. 找到 leftChild 最右叶子节点 tail，这个节点是当前以 leftChild 为根节点的树转换成链表后的最后一个节点（就是上面例子的 4）
4. 把根节点的右子树 “嫁接” 到 tail 后面（如下图所示）

     1
    / 
   2   
  / \   
 3   4  
      \
       5
        \
         6

1. 把 leftChild 移到根节点的右子树（如下图所示）

     1
      \
       2   
      / \   
     3   4  
          \
           5
            \
             6

1. 找到 leftChild 的第一个左子节点，重复第 1 步

Javascript

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @return {void} Do not return anything, modify root in-place instead.
 */
var flatten = function(root) {
    let cur = root
    while(cur) {
        if(cur.left) {
            const leftChild = cur.left
            let tail = leftChild
            while(tail.right) {
                tail = tail.right
            }
            tail.right = cur.right
            cur.right = cur.left
            cur.left = null
        }
        cur = cur.right
    }
};