解题思路#
题解#
230.二叉搜索树中第k小的元素#
中序遍历同时维护一个count记录当前遍历到的是第几个节点就可以，等于k时更新ans
甚至可以让k递减，k等于0时即为ans
199.二叉树的右视图#
很直观想到层序遍历，记录每层的最后一个即可
114.二叉树展开为链表#
第一遍自己想了一种后序遍历+子树重构（deepseek总结），首先递归左右都展开为链表，然后把右子树加到左子树的最下面的节点
但是寻找这个节点的过程又浪费了不少时间
所以考虑正常的递归遍历，遍历右左中，采用头插法完美解决
437.路径总和#
题面：统计祖先到孩子的路径上节点总和为target的个数
这道题和560的思路是一样的，当二叉树退化为一个链表时，和560一样
而560其实就是第一题的变式，枚举右维护左+hash就可以，只不过枚举的是前缀和数组
==注意== ：有一点要注意，左子树比右子树更早遍历，左子树对哈希表的更新可能会影响到右子树 所以我们在左子树结束时要==撤销对hash表的更新==，这一点区别是由于二叉树和数组结构不同导致的
dfs = func(node *TreeNode, s int){
//s is prefixSum of node's parent node
//process border
if node == nil {return}
//renew prefixSum
s += node.Val
//find in hash
ans += hash[s-targetSum]
//renew hash
hash[s]++
//dfs
dfs(node.Left, s)
dfs(node.Right, s)
//undo hash renew
hash[s]--
}236.二叉树最近公共祖先lowest common ancestor（LCA）#
自己想了一种非常直观的做法，直接从root开始向下遍历，找到左右都不是CA的节点，即是LCA，否则向下递归
==怎样优化？==
需要找一些规律，人脑想的越多，代码复杂度就越低，越是直观的逻辑，代码复杂度就越高
对灵神代码的理解：
func lowestCommonAncestor(root, p, q *TreeNode) *TreeNode {
/*先忽略名字，直观来看函数体，此函数要从root找到的是:
p或q或左右子树含p，q的那个节点（三种可能的情况）
其实仔细分析：LCA只可能有以下两种情况：
1. p, q 是祖先后代关系，lca是pq中的一个。
2. p, q 不是祖先后代关系，lca是那个左右都含p, q的。
这样我们就明白了，该函数能满足上述的所有情况
*/
if root == nil || root == p || root == q {
return root
}
left := lowestCommonAncestor(root.Left,p,q)
right := lowestCommonAncestor(root.Right,p,q)
//case 1
if left != nil && right != nil {
return root
}
//case 2
if left != nil {
return left
}
return right
}124.二叉树最大路径和#
想用递归，但是发现单纯去把maxPathSum作为递归返回值是不恰当的 因为子结构是拐弯的，再往上会分叉，明显不合题意
仔细思考，这个最大路径其实是所谓“直径”，它有一个拐点，只用算出 这个拐点加上左右两边的最长链就可以了
所以我们就把问题转化成了，求某个节点向下的最长链，递归过程中顺带更新答案
func maxPathSum(root *TreeNode) int {
ans := -100000000
var dfs func(node *TreeNode) int
dfs = func(node *TreeNode) int{
//返回以node为最高节点的最长链长
//边界处理
if node == nil {
return 0
}
//递归得左右最长链长
left := dfs(node.Left)
right := dfs(node.Right)
//顺带处理最大路径和逻辑
ans = max(ans, node.Val+left+right)
//返回结果，如果最长链是负数，这个信息没有保存的必要，返回0
return max(max(left, right) + node.Val, 0)
}
dfs(root)
return ans
}