[数据结构] Tree

[ylqi007]

Tree

处理 Tree 问题时，有几个要点可以考虑

1. 通常会用到 recursion，即对于当前树和子树的处理是类似的，即 process(root) 与 process(root.left) and process(root.right)
2. 考虑 edge cases 的处理，比如 null 节点，叶子节点等。
3. 分析对一个节点的处理，然后扩展到其他节点的处理。
4. 考虑对一个阶段的处理时，需不需要有返回值。

关于需不需要有返回值的例子: 关于 Tree 的问题，一般都会用到 recursion，只需要集中考虑每个节点如何处理。比如要返回什么、要更新什么。

• 129. Sum Root to Leaf Numbers
  • 本题中，主要要考虑空节点和叶子节点的处理情况，处理每个节点时不需要返回值。遇到空节点，不做任何处理，也无返回值。遇到叶子节点，更新 totalSum。遇到其他节点，不更新 totalSum，只是继续向下继续处理。
• 124. Binary Tree Maximum Path Sum
  • 本题中，处理每个节点时，返回到以本节点为终点的最大pathSum，同时还要尝试更新全局的最大路径和。因此需要有返回值。