胖头龙的咸鱼刷题笔记-算法篇

持续关注，持续关注

楼主好厉害啊 感觉成神了 佩服佩服

怎么给楼主加米呀？写的太好了！

楼主很有想法，赞！

真学霸假扮学弱吃offer

持续关注，楼主加油！

感谢lz分享，很有用，感觉思路清晰多了

感谢楼主的分享！

第八章 二叉树与递归


基本问题：
（1）理解二叉树、平衡二叉树、二叉搜索树的关系和概念。
（2）理解递归的概念和方法，递归三要素。
（3）在解决递归问题的时候，有时可以返回多个值（Python），或者用一个额外的class包装多个值（Java）。
（4）熟练掌握用递归和非递归的方式分别前序、中序、后序遍历二叉树的方法。
（5）理解掌握分治和遍历的区别和联系。
（6）理解掌握top-down, buttom-up的思路。
（7）理解掌握二叉树上的Iterator。


二叉树与递归 题目列表：
（必背：紫色；核心：蓝色；重点：绿色；普通：黄色；默认是LeetCode，如果是LintCode会以Lint开头）

因为二叉树上的递归很多时候既可以用分治，也可以用遍历，并不是哪一种方法总能最优。
所以我们按相似题目分类，而不是按解法分类。


二叉树前中后序遍历（需要熟练掌握非递归方式）：
94. Binary Tree Inorder Traversal
https://leetcode.com/problems/binary-tree-inorder-traversal/

144. Binary Tree Preorder Traversal
https://leetcode.com/problems/binary-tree-preorder-traversal/

145. Binary Tree Postorder Traversal
https://leetcode.com/problems/binary-tree-postorder-traversal/


反向复原二叉树：
105. Construct Binary Tree from Preorder and Inorder Traversal
https://leetcode.com/problems/co ... -inorder-traversal/

106. Construct Binary Tree from Inorder and Postorder Traversal
https://leetcode.com/problems/co ... ostorder-traversal/

889. Construct Binary Tree from Preorder and Postorder Traversal
https://leetcode.com/problems/co ... ostorder-traversal/


Iterator相关：
173. Binary Search Tree Iterator
https://leetcode.com/problems/binary-search-tree-iterator/

230. Kth Smallest Element in a BST
https://leetcode.com/problems/kth-smallest-element-in-a-bst/

285. Inorder Successor in BST
https://leetcode.com/problems/inorder-successor-in-bst/

270. Closest Binary Search Tree Value
https://leetcode.com/problems/closest-binary-search-tree-value/

272. Closest Binary Search Tree Value II
https://leetcode.com/problems/cl ... arch-tree-value-ii/

510. Inorder Successor in BST II
https://leetcode.com/problems/inorder-successor-in-bst-ii/

Lint-915. Inorder Predecessor in BST II
https://www.lintcode.com/problem ... -in-bst/description


判断树的形态：
98. Validate Binary Search Tree
https://leetcode.com/problems/validate-binary-search-tree/

100. Same Tree
https://leetcode.com/problems/same-tree/

101. Symmetric Tree
https://leetcode.com/problems/symmetric-tree/

110. Balanced Binary Tree
https://leetcode.com/problems/balanced-binary-tree/


子树相关问题：
111. Minimum Depth of Binary Tree
https://leetcode.com/problems/minimum-depth-of-binary-tree/

104. Maximum Depth of Binary Tree
https://leetcode.com/problems/maximum-depth-of-binary-tree/

333. Largest BST Subtree
https://leetcode.com/problems/largest-bst-subtree/

Lint-596. Minimum Subtree
https://www.lintcode.com/problem/minimum-subtree/description

Lint-597. Subtree with Maximum Average
https://www.lintcode.com/problem ... average/description


路径相关问题：
112. Path Sum
https://leetcode.com/problems/path-sum/

113. Path Sum II
https://leetcode.com/problems/path-sum-ii/

124. Binary Tree Maximum Path Sum
https://leetcode.com/problems/binary-tree-maximum-path-sum/

Lint-475. Binary Tree Maximum Path Sum II
https://www.lintcode.com/problem ... -sum-ii/description

298. Binary Tree Longest Consecutive Sequence
https://leetcode.com/problems/bi ... nsecutive-sequence/

549. Binary Tree Longest Consecutive Sequence II
https://leetcode.com/problems/bi ... cutive-sequence-ii/

Lint-619. Binary Tree Longest Consecutive Sequence III
https://www.lintcode.com/problem ... nce-iii/description


LCA问题：
236. Lowest Common Ancestor of a Binary Tree
https://leetcode.com/problems/lo ... r-of-a-binary-tree/

Lint-474. Lowest Common Ancestor II
https://www.lintcode.com/problem ... stor-ii/description

Lint-578. Lowest Common Ancestor III
https://www.lintcode.com/problem ... cestor-iii/solution


其他：
199. Binary Tree Right Side View
https://leetcode.com/problems/binary-tree-right-side-view/

513. Find Bottom Left Tree Value
https://leetcode.com/problems/find-bottom-left-tree-value/

331. Verify Preorder Serialization of a Binary Tree
https://leetcode.com/problems/ve ... n-of-a-binary-tree/

449. Serialize and Deserialize BST
https://leetcode.com/problems/serialize-and-deserialize-bst/

114. Flatten Binary Tree to Linked List
https://leetcode.com/problems/flatten-binary-tree-to-linked-list/

楼主太赞了👍 总结的很到位