/images/gravatar2.jpg

Steven Lin

[Golang][Leetcode][BinaryTree]刷題系列-654-Maximum Binary Tree

654. Maximum Binary Tree Level : Medium 原題連結 :Click 題目 : You are given an integer array nums with no duplicates. A maximum binary tree can be built recursively from nums using the following algorithm: Create a root node whose value is the maximum value in nums. Recursively build the left subtree on the subarray prefix to the left of the maximum value. Recursively build the right subtree on the subarray suffix to the right of the maximum value.

[Golang][Leetcode][BinaryTree]刷題系列-105-Construct Binary Tree from Preorder and Inorder Traversal

105. Construct Binary Tree from Preorder and Inorder Traversal Level : Medium 原題連結 :Click 題目 : Given two integer arrays preorder and inorder where preorder is the preorder traversal of a binary tree and inorder is the inorder traversal of the same tree, construct and return the binary tree. Example : Note Example 1: Input: preorder = [3,9,20,15,7], inorder = [9,3,15,20,7] Output: [3,9,20,null,null,15,7] Example 2: Input: preorder = [-1], inorder = [-1] Output: [-1]

[Golang][Leetcode][BinaryTree]刷題系列-106-Construct Binary Tree from Inorder and Postorder Traversal

106. Construct Binary Tree from Inorder and Postorder Traversal Level : Medium 原題連結 :Click 題目 : Given two integer arrays inorder and postorder where inorder is the inorder traversal of a binary tree and postorder is the postorder traversal of the same tree, construct and return the binary tree. Example : Note Example 1: Input: inorder = [9,3,15,20,7], postorder = [9,15,7,20,3] Output: [3,9,20,null,null,15,7] Example 2: Input: inorder = [-1], postorder = [-1] Output: [-1]

[Golang][Leetcode][BinaryTree]刷題系列-112-Path Sum

112. Path Sum Level : Easy 原題連結 :Click 題目 : Given the root of a binary tree and an integer targetSum, return true if the tree has a root-to-leaf path such that adding up all the values along the path equals targetSum. A leaf is a node with no children. Example : Note Example 1: Input: root = [5,4,8,11,null,13,4,7,2,null,null,null,1], targetSum = 22 Output: true Example 2: Input: root = [1,2,3], targetSum = 5 Output: false

[Golang][Leetcode][BinaryTree]刷題系列-513-Find Bottom Left Tree Value

513. Find Bottom Left Tree Value Level : Medium 原題連結 :Click 題目 : Given the root of a binary tree, return the leftmost value in the last row of the tree. Example : Note Example 1: Input: root = [2,1,3] Output: 1 Example 2: Input: root = [1,2,3,4,null,5,6,null,null,7] Output: 7 解題思路 : 這題需要你找到最後一排leave中最左邊的那個node的value 首先既然要找leave就必須使用dfs去把每一個leave visit一遍,並同時記錄該leave的level當遇到比當前紀錄的leave有更大的level時,替換掉他 這時候有些朋友可能會問那怎麼知道他是不是最左邊呢,這時候就可以用兩個小地方去控管 這題的寫法需要將visit left node的recursive code寫在visit right node的前面,這樣就能確保他是從左邊開始visit到右邊 因為是從左邊visit到右邊,所以我們需要當 maxLevel < curLevel 而不是 maxLevel <= curLevel時做替換,因為先visit的node必定比後進來的node還要左邊 Recursive解法 time complexity: O(n) , space complexity: O(1) Runtime: 4 ms, faster than 96.

[Golang][Leetcode][BinaryTree]刷題系列-404-Sum of Left Leaves

404. Sum of Left Leaves Level : Easy 原題連結 :Click 題目 : Given the root of a binary tree, return the sum of all left leaves. Example : Note Example 1: Input: root = [3,9,20,null,null,15,7] Output: 24 Explanation: There are two left leaves in the binary tree, with values 9 and 15 respectively. Example 2: Input: root = [1] Output: 0 解題思路 : 這題是用recursive的方式實現DFS的概念(大部分有關於leaves的題目都可以往DFS的方向去思考) 題目需要把每一個left leaves加起來,判斷一個leave是否為left leaves就是他是否是上一個node的left children 這裡提供兩個解法,兩個解法大同小異,一個是straight forward的去寫出邏輯判斷node.