题目地址(236. 二叉树的最近公共祖先)

https://leetcode-cn.com/problems/lowest-common-ancestor-of-a-binary-tree/

题目描述

  1. 给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。
  3. 百度百科中最近公共祖先的定义为：“对于有根树 T 的两个节点 p、q，最近公共祖先表示为一个节点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。”
  7. 示例 1：
  9. 输入：root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 1
  10. 输出：3
  11. 解释：节点 5 和节点 1 的最近公共祖先是节点 3 。
  14. 示例 2：
  16. 输入：root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 4
  17. 输出：5
  18. 解释：节点 5 和节点 4 的最近公共祖先是节点 5 。因为根据定义最近公共祖先节点可以为节点本身。
  21. 示例 3：
  23. 输入：root = [1,2], p = 1, q = 2
  24. 输出：1
  29. 提示：
  31. 树中节点数目在范围 [2, 105] 内。
  32. -109 <= Node.val <= 109
  33. 所有 Node.val 互不相同 。
  34. p != q
  35. p 和 q 均存在于给定的二叉树中。

前置知识


公司

  • 暂无

思路

image.png
如果要找的是7和5的话 遇到7直接返回7 最后的结果就是7
找到 pq就返回pq 没找到就返回null 一边返回null就返回另一边 两边都不为null说明当前root就是最大的公共祖先

关键点

  1. 求最小公共祖先，需要从底向上遍历，那么二叉树，只能通过后序遍历（即：回溯）实现从低向上的遍历方式。
  2. 在回溯的过程中，必然要遍历整颗二叉树，即使已经找到结果了，依然要把其他节点遍历完，因为要使用递归函数的返回值（也就是代码中的left和right）做逻辑判断。
  3. 要理解如果返回值left为空，right不为空为什么要返回right，为什么可以用返回right传给上一层结果。

代码

  • 语言支持：Java

Java Code:

  2. /**
  3.  * Definition for a binary tree node.
  4.  * public class TreeNode {
  5.  *     int val;
  6.  *     TreeNode left;
  7.  *     TreeNode right;
  8.  *     TreeNode(int x) { val = x; }
  9.  * }
  10.  */
  11. class Solution {
  12.         //递归的返回值 如果遇到qp就返回 参数就是节点和qp
  13.         public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
  14.             //递归中止条件 当root为以下三种情况就返回
  15.             if (root == p || root == q || root == null) {
  16.                 return root;
  17.             }
  18.             //使用后序遍历
  19.             TreeNode left = lowestCommonAncestor(root.left, p, q);
  20.             TreeNode right = lowestCommonAncestor(root.right, p, q);
  21.             //情况1 当两边都为null 返回null
  22.             if (left == null && right == null) {
  23.                 return null;
  24.                 //当一边为空 返回另一边的节点
  25.             } else if (left == null && right != null) {
  26.                 return right;
  27.             } else if (left != null && right == null) {
  28.                 return left;
  29.                 //到这个位置就是两边都不为空的情况 返回root
  30.             } else {
  31.                 return root;
  32.             }
  33.         }
  34.     }

复杂度分析

令 n 为数组长度。

  • 时间复杂度：236. 二叉树的最近公共祖先 2 - 图2#card=math&code=O%28n%29&id=IBAYm)
  • 空间复杂度：236. 二叉树的最近公共祖先 2 - 图3#card=math&code=O%28n%29&id=eAmh6)