iT邦幫忙

2017 iT 邦幫忙鐵人賽
DAY 14
0
自我挑戰組

LeetCode - 30 Days系列 第 14

[Leetcode-14/30][Tree] #114 Flatten Binary Tree to Linked List

#114 Flatten Binary Tree to Linked List

同步發佈於 Github repo

題目難度:Medium

題目敘述:

Given a binary tree, flatten it to a linked list in-place.

For example,
Given

         1
        / \
       2   5
      / \   \
     3   4   6

The flattened tree should look like:

   1
    \
     2
      \
       3
        \
         4
          \
           5
            \
             6

題目解答:

/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
/**
 * @param {TreeNode} root
 * @return {void} Do not return anything, modify root in-place instead.
 */
const flatten = root => {
  if(!root || (!root.left && !root.right)) return;
  if(root.left) flatten(root.left);
  if(root.right) flatten(root.right);
  
  const tmpRight = root.right;
  root.right = root.left;
  root.left = null;
  
  while(root.right) root = root.right;
  root.right = tmpRight;
};

題目連結:114. Flatten Binary Tree to Linked List

解題說明:

今天是 tree 的第二篇,挑戰難度 Medium 的題目 114. Flatten Binary Tree to Linked List,而且這題還會跟前一個主題 Linked List 有點關係,算是蠻綜合又有趣的題目。

題意是給我們一個 Binary Tree,然後要我們把這個 tree 裡的節點由小到大組成一個 Linked List
想法和前一題蠻像的,我們 DFS + 遞迴的方式解。

解題步驟:

  • 步驟 1.
    這題一樣只要一個步驟就可以解完,
    想法是先利用 DFS 找到最左子節點(此時該節點的 root.leftroot.right 都是 null),
    然後回到其父節點,先將右節點跟父節點斷開,
    然後把左節點接到右節點上,並且把左節點設為 null
    最後再把 原本的右節點 連到到 新右節點的右節點 上,
    最後再回到上一個父節點繼續做相同的操作。

    操作流程如下圖,

     1
    / \
   2   5
  / \   \
 3   4   6

     1
    / \
   2   5
    \   \
     3   6
      \    
       4

   1
    \
     2
      \
       3
        \
         4
          \
           5
            \
             6

完成!

const flatten = root => {
  if(!root || (!root.left && !root.right)) return;
  if(root.left) flatten(root.left);
  if(root.right) flatten(root.right);
  
  const tmpRight = root.right;
  root.right = root.left;
  root.left = null;
  
  while(root.right) root = root.right;
  root.right = tmpRight;
};

上一篇
[Leetcode-13/30][Tree] #226 Invert Binary Tree
下一篇
[Leetcode-15/30][Tree] #129 Sum Root to Leaf Numbers
系列文
LeetCode - 30 Days30

尚未有邦友留言

立即登入留言