二叉树遍历的问题
Binary Tree preorder traversal ,inorder traversal, postorder traversal
in 3 ways : Recursive, iterative and Morris solution( space:O(1))
Iterative : while( cur || !st.empty())
BST问题
98.Validate Binary Search Tree
Inorder traversal 用一个flag 来判断是否是BST第一个点。
preorder traversal 传min 和max 给下一层来限定范围
286.Inorder Successor in BST.
如果值大于或等于节点的值 就只能往右子树找，和左子树没关系了，
反之root为备选节点 如果递归左子树返回nullptr则选择root做为succ 反之选择返回的节点为succ。
2种写法 一种cursive 另一种 iterative
173.Binary Search Tree Iterator
一个stack存节点 findnext push 近right的节点。
96.Unique Binary Search Trees
动态规划 左边子树个数为0-n-1 右边子树个数位0-n-1 将每种对于的情况相乘并相加可以得到n个元素的 unique BST.
Unique Binary Search Trees ii
递归的方法做 bottom up 比较复杂(要多练习)
Closest Binary Search Tree Value i
- 找到离target最近的一个node val。
- 如果 target < root->val 就去看左子树 并且判断是否空。
- 否则看右子树 并且得到一个最小的 取差值返回 离target更近的点。
Closest Binary Search Tree Value ii(hard) - Inorder 以及用一个vector 来存k个元素 类似滑动窗口
- 两个stack ,Pred and Succ 来存前驱节点和后驱节点. (想不到)
LCA的问题
LCA of BST 如果root的值比两个中较大的还大 就去左子树找LCA 如果 root比两个中较小的还小 就去右子树找， 反之说明root在p 和 q之间的LCA。
LCA of BT 和上一道类似只是要判断左右子树递归结果。
路径和的问题
Binary Tree Path
Path sum 1 2 3 4
- root to leaf path so we need to check whether the node is a leaf.
- Same with 1 But using backtracking
- Still using a dfs to search for path and use the main function to recursive search from the other root.
- some manipulation to those numbers and actually is same with 1
binary Tree maximum path sum: divide and conquer
Sum Root to Leaf Number : same as path sum 2
Sum of Left Leaves : dfs traversal with a flag
修改结构的问题
108 convert sorted array into BST
preorder divide and conquer
109 Convert sorted list into BST
if you do it in preorder the time complexity will be O(nlogn) (fast and slow pointers) Traverse the list twice: the first time to get the length, the second time is for inorder construction which is linear.
114 Flatten binary tree to linked list
divide and conquer （类似 BST to DLL）
去年面bb的题 binary tree to doubly linked list
3种方法 1)preorder divide and conquer 2) inorder traversal 3) morris solution
比较靠后的问题
538 Convert BST to Greater Tree
从右子树开始inorder 非常ez
563 Binary Tree Tilt
ez 直接d&q 返回子树和用个全局变量存differ
501 Find Mode in Binary Search Tree
遍历两遍树 inorder traversal 是有序的， 第一遍找最大的frequence 第二遍就把freq等于maxfreq的树push进数组。
508 Most Frequent SubTree Sum
又是一道变种 核心思想还说path sum + most freq