iT邦幫忙

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

LeetCode - 30 Days系列 第 13

[Leetcode-13/30][Tree] #226 Invert Binary Tree

#226 Invert Binary Tree

同步發佈於 Github repo

題目難度:Easy

題目敘述:

Invert a binary tree.

     4
   /   \
  2     7
 / \   / \
1   3 6   9

to

     4
   /   \
  7     2
 / \   / \
9   6 3   1

Trivia:
This problem was inspired by this original tweet by Max Howell:
Google: 90% of our engineers use the software you wrote (Homebrew), but you can’t invert a binary tree on a whiteboard so fuck off.

題目解答:

/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
/**
 * @param {TreeNode} root
 * @return {TreeNode}
 */
const invertTree = root => {
  if(!root) return root;
  
  const tmpLeft = root.left;
  root.left = invertTree(root.right);
  root.right = invertTree(tmpLeft);
  
  return root;
};

題目連結:226. Invert Binary Tree

解題說明:

又進入到新的章節囉!這三天的主題是 tree
tree 基本上就二元樹 Binary Tree,也就是樹上的每一個節點都有一個 左節點 跟一個 右節點
tree 通常以 functionclass 的方式表現,如下是以 java 寫的,

class TreeNode{
  int value;
  TreeNode left;
  TreeNode right;
}

Binary Tree 只是最基本 tree 的形式,還有更多不同種的 tree 如:

  1. Binary Search Tree
  2. Balanced Tree, Unbalanced Tree
  3. Full Binary Tree
    ...

等之後如果題目有用到再仔細解釋!

今天是 tree 的第一篇,照慣例我們先來寫一個難度 Easy 的題目 226. Invert Binary Tree

題意很清楚,給你一個 Binary Tree 要你以最開頭為中心來反轉它,如此而已~~~

解題步驟:

  • 步驟 1.
    這題只要五行,用遞迴的方式去跑就行了~

    想法是,如果節點 root 不存在就代表遞迴結束,
    然後把左節點 root.left 設為右節點 root.right 的遞迴結果,
    把右節點 root.right 設為左節點 root.left 的遞迴結果,
    就這樣,完成!

const invertTree = root => {
  if(!root) return root;
  
  const tmpLeft = root.left;
  root.left = invertTree(root.right);
  root.right = invertTree(tmpLeft);
  
  return root;
};

上一篇
[Leetcode-12/30][Linked List] #2 Add Two Numbers
下一篇
[Leetcode-14/30][Tree] #114 Flatten Binary Tree to Linked List
系列文
LeetCode - 30 Days30

尚未有邦友留言

立即登入留言