iT邦幫忙

第 11 屆 iThome 鐵人賽

DAY 28
1
Software Development

透過 LeetCode 解救美少女工程師的演算法人生系列 第 28

[Day 28] 演算法刷題 LeetCode 114. Flatten Binary Tree to Linked List (Medium)


題目


https://leetcode.com/problems/flatten-binary-tree-to-linked-list/

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

For example, given the following tree:

Example:

    1
   / \
  2   5
/ \   \
3   4   6

The flattened tree should look like:

1
\
  2
   \
    3
     \
      4
       \
        5
         \
          6

解答


C#

/**
* Definition for a binary tree node.
* public class TreeNode {
*     public int val;
*     public TreeNode left;
*     public TreeNode right;
*     public TreeNode(int x) { val = x; }
* }
*/
public class Solution {
    public void Flatten(TreeNode root)
    {
        Flatten(root, null);
    }
    
    private TreeNode Flatten(TreeNode current, TreeNode cut)
    {
        if (current == null)
            return cut;
        cut = Flatten(current.right, cut);
        cut = Flatten(current.left, cut);
        current.right = cut;
        current.left = null;
        return current;
    }
}

結果


Runtime: 92 ms, faster than 97.29% of C# online submissions.

Memory Usage: 24 MB, less than 33.33% of C# online submissions.

Time Complexity: O(n)

Space Complextiy: O(1)


為什麼我要這樣做?


今天終於來到最後一題與 Tree 相關的演算法啦!還沒跟上的人記得往前複習 ↓
[Day 22] 演算法刷題 LeetCode 101. Symmetric Tree (Easy) Part 1 - Recursion
[Day 23] 演算法刷題 LeetCode 101. Symmetric Tree (Eas
y) Part 2 - Iteration

[Day 24] 演算法刷題 LeetCode 104. Maximum Depth of Binary Tree (Easy)
[Day 25] 演算法刷題 LeetCode 543. Diameter of Binary Tree (Easy)
[Day 26] 演算法刷題 LeetCode 226. Invert Binary Tree (Easy)
[Day 27] 演算法刷題 LeetCode 617. Merge Two Binary Trees (Easy)

  1. 先實作 privateFaltten(TreeNode current, TreeNode ) 的 method
    • current 為要 接上去 的 node,cut 則是被 剪下來 的 node
    • 判斷若 current 為 null 時,回傳 cut
    • cut 則用遞迴的方式去巡覽,並找出要被剪下來的 cut node
    • 找到後,此時被要接上的 current.right = cutcurrent.left 則清空設為 null
    • 回傳 current ,並為下一輪遞迴做準備
  2. 原本要實作的 Flatten(TreeNode root) 呼叫 private Flatten(root, null); 即可

示意圖

如果看文字敘述不是很明確的話,可以看下面的示意圖。

Step 1

Step 2

Step 3


以上就是這次 LeetCode 刷題的分享啦!
如果其它人有更棒的想法及意見,請留言或寄信(t4730@yahoo.com.tw) 給我。
那我們就下回見囉 /images/emoticon/emoticon07.gif


上一篇
[Day 27] 演算法刷題 LeetCode 617. Merge Two Binary Trees (Easy)
下一篇
[Day 29] 演算法刷題 LeetCode 55. Jump Game (Medium)
系列文
透過 LeetCode 解救美少女工程師的演算法人生31
圖片
  直播研討會
圖片
{{ item.channelVendor }} {{ item.webinarstarted }} |
{{ formatDate(item.duration) }}
直播中

尚未有邦友留言

立即登入留言