 # Tree - 129. Sum Root to Leaf Numbers

129. Sum Root to Leaf Numbers Given a binary tree containing digits from 0-9 only, each root-to-leaf path could represent a number. An example is the root-to-leaf path 1->2->3 which represents the number 123. Find the total sum of all root-to-leaf numbers. Note: A leaf is a node with no children. Example: Input: [1,2,3] 1 / \ 2 3 Output: 25 Explanation: The root-to-leaf path 1->2 represents the number 12. The root-to-leaf path 1->3 represents the nu.... # Tree - 113. Path Sum II

113. Path Sum II Given a binary tree and a sum, find all root-to-leaf paths where each path’s sum equals the given sum. Note: A leaf is a node with no children. Example: Given the below binary tree and sum = 22, 5 / \ 4 8 / / \ 11 13 4 / \ / \ 7 2 5 1 Return: [ [5,4,11,2], [5,8,4,5] ] 思路： 题目意思是求出所有根节点到叶子结点路径和为sum的结果。递归求解，找到叶子节点比较sum就可以 代码： go： /** * Definition for a binary tree node. * type TreeNode struct { * Val int * Left *TreeNode * Right *TreeNode * } */ func pathSum(roo.... # Tree - 112. Path Sum

112. Path Sum Given a binary tree and a sum, determine if the tree has a root-to-leaf path such that adding up all the values along the path equals the given sum. Note: A leaf is a node with no children. Example: Given the below binary tree and sum = 22, 5 / \ 4 8 / / \ 11 13 4 / \ \ 7 2 1 return true, as there exist a root-to-leaf path 5->4->11->2 which sum is 22. 思路： 题目意思是问根节点叶子节点的路径有没有求和之后等于sum，很简单的题目，和257题类似，递归求解。 代码： go： /** * Definition for a binary tr.... # Tree - 257. Binary Tree Paths

257. Binary Tree Paths Given a binary tree, return all root-to-leaf paths. Note: A leaf is a node with no children. Example: Input: 1 / \ 2 3 \ 5 Output: ["1->2->5", "1->3"] Explanation: All root-to-leaf paths are: 1->2->5, 1->3 思路： 题目意思是从root节点走到叶子节点一共有多少路径，采用递归求解，和先序遍历类似，找到叶子节点就把路径保存下来。 代码： go： /** * Definition for a binary tree node. * type TreeNode struct { * Val int * Left *TreeNode * Right *TreeNode * } */ func binaryTreePaths(root *TreeNode) []string { var r.... # Tree - 226. Invert Binary Tree

226. Invert Binary Tree Invert a binary tree. Example: Input: 4 / \ 2 7 / \ / \ 1 3 6 9 Output: 4 / \ 7 2 / \ / \ 9 6 3 1 思路： 递归求解翻转每个不为nil的节点 代码： go： /** * Definition for a binary tree node. * type TreeNode struct { * Val int * Left *TreeNode * Right *TreeNode * } */ func invertTree(root *TreeNode) *TreeNode { if root == nil { return root } root.Left, root.Right = root.Right, root.Left invertTree(root.Left) invertTree(root.Right) return root } # Tree - 101. Symmetric Tree

101. Symmetric Tree Given a binary tree, check whether it is a mirror of itself (ie, symmetric around its center). For example, this binary tree [1,2,2,3,4,4,3] is symmetric: 1 / \ 2 2 / \ / \ 3 4 4 3 But the following [1,2,2,null,3,null,3] is not: 1 / \ 2 2 \ \ 3 3 Note: Bonus points if you could solve it both recursively and iteratively. 思路： 题目意思是判断一棵树是不是对称的，可以用迭代或者递归来做 代码： go： /** * Definition for a binary tree node. * type TreeNode struct { * Val int * Left *Tr.... # Tree - 100. Same Tree

100. Same Tree Given two binary trees, write a function to check if they are the same or not. Two binary trees are considered the same if they are structurally identical and the nodes have the same value. Example 1: Input: 1 1 / \ / \ 2 3 2 3 [1,2,3], [1,2,3] Output: true 思路： 题目很简单，判断两个树是否相同，只要随便使用一种方式遍历一次树就可以，这里使用先序遍历来做。 代码： go： /** * Definition for a binary tree node. * type TreeNode struct { * Val int * Left *TreeNode * Right *TreeNode * } */ //recursive func isSameTree(p *TreeNode, q.... # Tree - 102. Binary Tree Level Order Traversal

102. Binary Tree Level Order Traversal Given a binary tree, return the level order traversal of its nodes’ values. (ie, from left to right, level by level). For example: Given binary tree [3,9,20,null,null,15,7], 3 / \ 9 20 / \ 15 7 return its level order traversal as: [ , [9,20], [15,7] ] 思路： 层序遍历二叉树，这一题和637题很像，637是求每一层的平均值，这一题只让打印出来，可以用bfs做，也可以使用dfs做，这里用bfs做，有递归写法和非递归写法，非递归写法使用了队列在存储下一层要遍历的节点。 代码： go： /** * Definition for a binary tree node. * type TreeNode struct {.... # Tree - 145. Binary Tree Postorder Traversal

145. Binary Tree Postorder Traversal Given a binary tree, return the postorder traversal of its nodes’ values. Example: Input: [1,null,2,3] 1 2 / 3 Output: [3,2,1] Follow up: Recursive solution is trivial, could you do it iteratively? 思路： 二叉树后序遍历，递归和迭代来做，迭代也是使用list容器来充当栈，后序遍历和前序后序遍历主要特点在于父节点会被访问两次，所以使用一个辅助指针preVisited来记录是否是第二次访问这个节点。 代码： go： /** * Definition for a binary tree node. * type TreeNode struct { * Val int * Left *TreeNode * Right *TreeNode * } */ /* .... # Tree - 94. Binary Tree Inorder Traversal

94. Binary Tree Inorder Traversal Given a binary tree, return the inorder traversal of its nodes’ values. Example: Input: [1,null,2,3] 1 2 / 3 Output: [1,3,2] Follow up: Recursive solution is trivial, could you do it iteratively? 思路： 二叉树的中序遍历，先访问左子树然后中间节点然后右子树。迭代也是使用list容器来充当栈 代码： go ： /** * Definition for a binary tree node. * type TreeNode struct { * Val int * Left *TreeNode * Right *TreeNode * } */ // recursive /*func inorderTraversal(root *TreeNode) []int { var res [.... # Tree - 144. Binary Tree Preorder Traversal

144. Binary Tree Preorder Traversal Given a binary tree, return the preorder traversal of its nodes’ values. Example: Input: [1,null,2,3] 1 2 / 3 Output: [1,2,3] Follow up: Recursive solution is trivial, could you do it iteratively? 思路： 二叉树的先序遍历，递归求解和迭代，迭代使用list容器的链表代替栈来做 代码： go： /** * Definition for a binary tree node. * type TreeNode struct { * Val int * Left *TreeNode * Right *TreeNode * } */ // recursive /*func preorderTraversal(root *TreeNode) []int { var .... # Dynamic Programming - 91. Decode Ways

91. Decode Ways A message containing letters from A-Z is being encoded to numbers using the following mapping: 'A' -> 1 'B' -> 2 ... 'Z' -> 26 Given a non-empty string containing only digits, determine the total number of ways to decode it. Example 1: Input: “12” Output: 2 Explanation: It could be decoded as “AB” (1 2) or “L” (12). Example 2: Input: “226” Output: 3 Explanation: It could be decoded as “BZ” (2 26), “VF” (22 6), or “BBF” (2 2 6). 思路：.... # Dynamic Programming - 213. House Robber II

213. House Robber II You are a professional robber planning to rob houses along a street. Each house has a certain amount of money stashed. All houses at this place are arranged in a circle. That means the first house is the neighbor of the last one. Meanwhile, adjacent houses have security system connected and it will automatically contact the police if two adjacent houses were broken into on the same night. Given a list of non-negative integers representing the amount of mo.... # Dynamic Progamming - 198. House Robber

198. House Robber You are a professional robber planning to rob houses along a street. Each house has a certain amount of money stashed, the only constraint stopping you from robbing each of them is that adjacent houses have security system connected and it will automatically contact the police if two adjacent houses were broken into on the same night. Given a list of non-negative integers representing the amount of money of each house, determine the maximum amount of money you can rob.... # Dynamic Programming - 221. Maximal Square

221. Maximal Square Given a 2D binary matrix filled with 0’s and 1’s, find the largest square containing only 1’s and return its area. Example: Input: 1 0 1 0 0 1 0 1 1 1 1 1 1 1 1 1 0 0 1 0 Output: 4 思路： 题目意思是给一个矩阵，找出矩阵中最大的正方形面积，正方形里面全是1。使用动态规划的思想做，子问题就是对于任意一个值为1的网格，去比较网格上一个格和左边一格和左上角的网格所记录的最大正方形边长。然后当前格的最小正方形边长就等于前面三者最小值加一，所以状态转移方程就是dp[i][j] = min{dp[i-1][j-1], dp[i][j-1], dp[i-1][j]}, dp[i][j]代表了第i行第j列位置为正方形的右下角，所能表示的最大正方形边长。初始条件和边界条件是第一行和第一列。 代码： go： func maximalSquare(matrix [][]by.... # Dynamic Programming - 174. Dungeon Game

174. Dungeon Game The demons had captured the princess (P) and imprisoned her in the bottom-right corner of a dungeon. The dungeon consists of M x N rooms laid out in a 2D grid. Our valiant knight (K) was initially positioned in the top-left room and must fight his way through the dungeon to rescue the princess. The knight has an initial health point represented by a positive integer. If at any point his health point drops to 0 or below, he dies immediately. Some of the rooms are guarded by.... # Dynamic Programming - 97. Interleaving String

97. Interleaving String Given s1, s2, s3, find whether s3 is formed by the interleaving of s1 and s2. Example 1: Input: s1 = “aabcc”, s2 = “dbbca”, s3 = “aadbbcbcac” Output: true Example 2: Input: s1 = “aabcc”, s2 = “dbbca”, s3 = “aadbbbaccc” Output: false 思路： 题目意思是指如果用s1和s2可以拼出s3就返回true，但注意拼接的时候是存在顺序的，就是用来拼接s1和s2的字符在s3中顺序需要和原来一样。考虑最后一步是s3的最后一个字母该来自于谁，之前的拼接出来的结果是否合法，就等价于一个拼接合法字符串加上s1或者s2最后一个字符等于最终结果，这就把问题退化为求上一个合法字符串拼接的问题，很明显，可以用动态规划来做. 如图： ( )s1.... # Dynamic Programming - 72. Edit Distance

72. Edit Distance Given two words word1 and word2, find the minimum number of operations required to convert word1 to word2. You have the following 3 operations permitted on a word: Insert a character Delete a character Replace a character Example 1: Input: word1 = “horse”, word2 = “ros” Output: 3 Explanation: horse -> rorse (replace ‘h’ with ‘r’) rorse -> rose (remove ‘r’) rose -> ros (remove ‘e’) Example 2: Input: word1 = “intention”, word2 = “e.... # Dynamic Programming - 64. Minimum Path Sum

64. Minimum Path Sum Given a m x n grid filled with non-negative numbers, find a path from top left to bottom right which minimizes the sum of all numbers along its path. Note: You can only move either down or right at any point in time. Example: Input: [   [1,3,1], [1,5,1], [4,2,1] ] Output: 7 Explanation: Because the path 1→3→1→1→1 minimizes the sum. 思路： 题目意思是给一个网格，找出左上角到右下角最短路径和，和62、63、120题很像，都是经典dp最值问题，子问题就是走到当前位置从哪个方向过来的数值最小。 代码： go： // time:.... # Dynamic Programming - 322. Coin Change

Coin Change You are given coins of different denominations and a total amount of money amount. Write a function to compute the fewest number of coins that you need to make up that amount. If that amount of money cannot be made up by any combination of the coins, return -1. Example 1: Input: coins = [1, 2, 5], amount = 11 Output: 3 Explanation: 11 = 5 + 5 + 1 Example 2: Input: coins = , amount = 3 Output: -1 Note: You may assume that you have an infinite number of each kind of coin. 思路： ....

Nothing just happens, it's all part of a plan.