二叉树

发表于： 分类于：
字数： 346 阅读：≈ 1分钟

灵神题单

自底向上dfs: 后序遍历

对于当前节点root做什么，需要它的子树的信息。

  1. LC 1110， 删点成林
  2. LC 1123 公共祖先

先序遍历

  1. LC 1026, 节点与其祖先之间的最大差值. (也可以postorder)

构造二叉树

105：前序和中序构造二叉树。直接 recursion 调用原函数，传入 inorder 和 pre-order 的切片即可。

直径

LC 543: return -1 if not root
LC 687
LC 124：最大路径和
LC 549: 返回当前节点到叶子节点的递增/递减的最大路径长度

2385. 感染二叉树需要的总时间🌟

Alt text diameter表示必须经过start节点的最大直径。
startDepth表示 start 到叶子节点的深度
res=max(diameter-startDepth, startDepth)

在更新 diameter 的时候，必须确保当前路径含有 start
dfs返回两个值。

深度：如果root这棵树不含有start, 返回root到叶子的深度；如果这棵树含有start，返回root到start的深度。
该树是否含有start，T/F