LouisLan的学习简记 👋🏼

题目地址 https://leetcode.com/problems/construct-binary-tree-from-preorder-and-inorder-traversal/ 题目描述 Given preorder and inorder traversal of a tree, construct the binary tree. Note: You may assume that duplicates do not exist in the tree. For example, given preorder = [3,9,20,15,7] inorder = [9,3,15,20,7] Return the following binary tree: 3 / \ 9 20 / \ 15 7 思路 这道题要求用先序和中序遍历来建立二叉树，跟之前那道 Construct Binary Tree from Inorder and Postorder Traversal 原理基本相同，针对这道题，由于先序的顺序的第一个肯定是根，所以原二叉树的根节点可以知道，题目中给了一....

题目地址 https://leetcode.com/problems/maximum-depth-of-binary-tree/ 题目描述 Given a binary tree, find its maximum depth. The maximum depth is the number of nodes along the longest path from the root node down to the farthest leaf node. Note: A leaf is a node with no children. Example: Given binary tree [3,9,20,null,null,15,7], 3 / \ 9 20 / \ 15 7 return its depth = 3. 思路 求二叉树的最大深度问题用到深度优先搜索 Depth First Search，递归的完美应用，跟求二叉树的最小深度问题原理相同，参见代码如下： C++ 解法一： class Solution { public: int maxDepth(TreeNode* r....

题目地址 https://leetcode.com/problems/binary-tree-zigzag-level-order-traversal/ 题目描述 Given a binary tree, return the zigzag level order traversal of its nodes' values. (ie, from left to right, then right to left for the next level and alternate between). For example: Given binary tree [3,9,20,null,null,15,7], 3 / \ 9 20 / \ 15 7 return its zigzag level order traversal as: [ [3], [20,9], [15,7] ] 思路 这道二叉树的之字形层序遍历是之前那道 Binary Tree Level Order Traversal 的变形，不同之处在于一行是从左到右遍历，下一行是从右往左遍历，交叉往返的之字形的层序遍历。....

题目地址 https://leetcode.com/problems/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,#,#,15,7}, 3 / \ 9 20 / \ 15 7 return its level order traversal as: [ [3], [9,20], [15,7] ] 思路 层序遍历二叉树是典型的广度优先搜索 BFS 的应用，但是这里稍微复杂一点的是，要把各个层的数分开，存到一个二维向量里面，大体思路还是基本相同的，建立一个 queue，然后先把根节点放进去，这时候找根节点的左右两个子节点，这时候去掉根节点，此时 queue 里的元素就是下一层的所有节点，用一个 for 循环遍历它们，然后存到一个一维向量里，....

题目地址 https://leetcode.com/problems/symmetric-tree/ 题目描述 Given a binary tree, check whether it is a mirror of itself (ie, symmetric around its center). For example, this binary tree is symmetric: 1 / \ 2 2 / \ / \ 3 4 4 3 But the following is not: 1 / \ 2 2 \ \ 3 3 Note: Bonus points if you could solve it both recursively and iteratively. 思路 判断二叉树是否是平衡树，比如有两个节点 n1, n2，我们需要比较 n1 的左子节点的值和 n2 的右子节点的值是否相等，同时还要比较 n1 的右子节点的值和 n2 的左子结点的值是否相等，以此类推比较完所有的左右两个节点。我们可以用递归和迭代两种方法来实现，写法不同，但是算法核心都一样。 关键点解析 代....

题目地址 https://leetcode.com/problems/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 Example 2: Input: 1 1 / \ 2 2 [1,2], [1,null,2] Output: false Example 3: Input: 1 1 / \ / \ 2 1 1 2 [1,2,1], [1,1,2] Output: false 思路 判断两棵树是否相同和之前的判断两棵树是否对称都是一样的原理，利用深度优先搜索 DFS 来递归。 关键点解析 ....

题目地址 https://leetcode.com/problems/recover-binary-search-tree/ 题目描述 Two elements of a binary search tree (BST) are swapped by mistake. Recover the tree without changing its structure. Example 1: Input: [1,3,null,null,2] 1 / 3 \ 2 Output: [3,1,null,null,2] 3 / 1 \ 2 Example 2: Input: [3,1,4,null,null,2] 3 / \ 1 4 / 2 Output: [2,1,4,null,null,3] 2 / \ 1 4 / 3 Follow up: A solution using O( n ) space is pretty straight forward. Could you devise a constant space solution? 思路 这道题要求我们复原一个二叉搜索树，说是其....

题目地址 https://leetcode.com/problems/validate-binary-search-tree/ 题目描述 Given a binary tree, determine if it is a valid binary search tree (BST). Assume a BST is defined as follows: The left subtree of a node contains only nodes with keys less than the node's key. The right subtree of a node contains only nodes with keys greater than the node's key. Both the left and right subtrees must also be binary search trees. Example 1: Input: 2 / \ 1 3 Output: true Example 2: 5 / \ 1 4 / \ 3 6 Output: fa....

题目地址 https://leetcode.com/problems/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 思路 这道求交织相错的字符串和之前那道 Word Break 的题很类似，就像我之前说的只要是遇到字符串的子序列或是匹配问题直接就上动态规划 Dynamic Programming，其他的都不要考虑，什么递归呀的都是浮云（当然带记忆数组的递归写法除外，因为这也可以算是 DP 的一种），千辛万苦的写了递归结果拿到 OJ 上妥妥 Time Limit Exceeded，能把人气昏了，所以还是直接....

题目地址 https://leetcode.com/problems/unique-binary-search-trees/ 题目描述 Given n , how many structurally unique BST's (binary search trees) that store values 1 ... n? Example: Input: 3 Output: 5 Explanation: Given _n_ = 3, there are a total of 5 unique BST's: 1 3 3 2 1 \ / / / \ \ 3 2 1 1 3 2 / / \ \ 2 1 2 3 思路 这道题实际上是 卡塔兰数 Catalan Numbe 的一个例子，如果对卡塔兰数不熟悉的童鞋可能真不太好做。话说其实我也是今天才知道的好嘛 -.-|||，为啥我以前都不知道捏？！为啥卡塔兰数不像斐波那契数那样人尽皆知呢，是我太孤陋寡闻么？！不过今天知道也不晚，不断的学习新的东西，这才是刷题的意义所在嘛！ 好了，废话不多说了，赶紧回到题目上来吧。我们先来看当 n = 1 的情况，只....