LeetCode题集整理- 树

• 要求：算法的时间复杂度应是线性的，不需要额外的存储空间。

那么如果其中的元素都出现三次，只有一个元素出现一次，该如何解决呢？

2、如何构造一个二叉树

• 树🌲是n(n>=0)个节点的有限集，且这些节点满足如下关系：

  • 1：有且仅有一个节点没有父亲，该节点为树的根，root。
  • 2: 除了根外，其余的每个节点都有且仅有一个父节点。
  • 3: 树中的每个节点都构成一个以它为根的树🌲。

• 二叉树在满足树的条件时，还满足如下条件：

  • 每个节点最多有两个孩子，这两个子树有左右之分，次序不可颠倒。

• 前序遍历：根节点->左子树->右子树
• 中序遍历：左子树->根节点->右子树
• 后序遍历：左子树->右子树->根节点

• 思考：

  • 使用何种数据结构存储遍历路径上的节点。
    • 从根节点深度遍历二叉树，先序遍历时，将该节点值存储至path栈中，用Vector实现，使用path_value累加节点值。

• 如何判断一个节点为叶子🍃节点？当遍历到叶子节点时应该做什么？

  • 当遍历到叶节点时，检查path_value值是否为sum,若为sum，则将path push进入result 结果中。

• 在树的前序 遍历时做什么？后序遍历做什么？

  • 后序遍历时，将该节点值从path栈中弹出，path_value减去节点值。

• 我们遍历从根节点到叶子的所有路径，定义sum为路径经过节点值之和，若sum等于给定值，我们就输出该条路径中的节点组成的vector。此题中的递归跳出条件为访问完成了叶子节点。

• 最近公共祖先： 两节点V与W的最近公共祖先u，满足在树上最低，且V， W两个节点都是u的子孙。
• 两个节点的公共祖先一定是从跟节点，到这两个节点的路径上。
• 由于求公共祖先中的最近公共祖先，那么即同时出现在这两条路径上的离跟节点最远的节点。
• 最终算法即：求p节点路径，q节点路径，两个路径上最后一个相同的节点。

6、给定一个二叉树，求其最大深度。最大深度是从根节点到最远叶节点的最长路径上的节点数。

思路：
根据树的结构特点，将其分为左子树和右子树两部分，根据递归先序遍历的思想将大问题转化为小问题，左右子树中深度最大的一棵即为该树结构的深度。