Description

面试题68 - II. 二叉树的最近公共祖先

难度：简单
给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。
百度百科中最近公共祖先的定义为：“对于有根树 T 的两个结点 p、q，最近公共祖先表示为一个结点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。”
例如，给定如下二叉树: root = [3,5,1,6,2,0,8,null,null,7,4]
剑指offer 68 - II. 二叉树的最近公共祖先 - 图1
示例 1:
输入: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 1
输出: 3
解释: 节点 5 和节点 1 的最近公共祖先是节点 3。
示例 2:
输入: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 4
输出: 5
解释: 节点 5 和节点 4 的最近公共祖先是节点 5。因为根据定义最近公共祖先节点可以为节点本身。

Solution

第一种解答：

寻找 root 根节点到达指定节点的路径，将问题转化为求链表的第一个公共节点，由于子节点没有指向父节点的链接，所以我们需要用栈或者其他容器来存储从 root 到达指定节点的路径。
剑指offer 68 - II. 二叉树的最近公共祖先 - 图2
以查找5， 4 节点为例，根节点 root 到达节点 5 的路径为 3->5， 根节点 root 到达节点4 的路径 3->5->2->4。用两个栈分别存储其对应的路径，问题就转化为求其路径上第一个相同的元素了

  1. class Solution {
  2.     Stack<TreeNode> stack1;
  3.     Stack<TreeNode> stack2;
  4.     public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
  5.        stack1 = new Stack<>();
  6.        stack2 = new Stack<>();
  7.        dfs(root, p, stack1);  // 求 root 到达 p 的路径
  8.        dfs(root, q, stack2);    // 求 root 到达 q 的路径
  10.        // 使两个栈的长度相同 
  11.        while(stack1.size() != stack2.size()){
  12.            if(stack1.size() > stack2.size())
  13.                 stack1.pop();
  14.            else
  15.                 stack2.pop();
  16.        }      
  17.         // 寻找栈顶相同的元素，此元素就是最近的公共祖先结点。
  18.        while(stack1.peek() != stack2.peek()){
  19.            stack1.pop();
  20.            stack2.pop();
  21.        }
  23.        return stack1.pop();
  24.     }
  26.     public boolean dfs(TreeNode root, TreeNode node, Stack<TreeNode> stack){
  27.         if(root == null)
  28.             return false;
  29.         stack.push(root);
  30.         if(root == node)
  31.             return true;   // 找到的情况
  32.         if(dfs(root.left, node, stack) || dfs(root.right, node, stack))
  33.             return true;   // 左右子树任意一个找到的情况
  34.         stack.pop();   // 路径没有指定的节点，弹出元素
  36.         return false;  // 其子树没有指定节点
  37.     }
  38. }

执行结果：
执行用时 :10 ms, 在所有 Java 提交中击败了41.03%的用户
内存消耗 :43.8 MB, 在所有 Java 提交中击败了100.00%的用户
参考评论区 ：

  1. public boolean dfs(TreeNode root, TreeNode node, Stack<TreeNode> stack){
  2.         if(root == null)
  3.             return false;
  4.         stack.push(root);
  5.         if(root == node)
  6.             return true;   // 找到的情况
  7.         if(dfs(root.left, node, stack) || dfs(root.right, node, stack))
  8.             return true;   // 左右子树任意一个找到的情况
  9.         stack.pop();   // 路径没有指定的节点，弹出元素
  11.         return false;  // 其子树没有指定节点
  12. }


第二种解答

递归遍历寻找
剑指offer 68 - II. 二叉树的最近公共祖先 - 图3
边界条件：
- root 为 null， 此时到达树的底部，返回 null 。
- root 等于 q 或者 root 等于p，返回该节点给父节点，父节点的子树存在寻找的节点。
- 如果当前节点的左右子树不为空，说明 p，q 存在于当前节点的子树中，当前节点即为最近公共祖先节点。
- 如果 left 或者 right 其中一个不为 null ，返回不为 null 的节点，两者为 null，返回 null。 

  1. class Solution
  2.     public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
  3.         if(root== null || root == p || root == q)  // 边界条件
  4.             return root;
  5.         // 
  6.         TreeNode  left = lowestCommonAncestor(root.left, p, q);
  7.         TreeNode right = lowestCommonAncestor(root.right, p, q);
  9.         // 左右子树都不为空，root 为当前最近公共祖先  
  10.         if(left != null && right != null)
  11.             return root;
  13.         // left 为空则放回 right， 两者为空则返回 null
  14.         return left != null ? left : right;    
  15.     }
  16. }

执行结果：
执行用时 :8 ms, 在所有 Java 提交中击败了90.06%的用户。
内存消耗 :41.6 MB, 在所有 Java 提交中击败了100.00%的用户。