题目

描述

给定一棵二叉树(保证非空)以及这棵树上的两个节点对应的val值 o1 和 o2，请找到 o1 和 o2 的最近公共祖先节点。
注：本题保证二叉树中每个节点的val值均不相同。

方法一

思路

题目要求找到二叉树中离两个节点o1，o2最近的公共祖先，可以先找出o1的所有祖先节点，然后再由近到远遍历以o1的祖先节点（包括o1节点）为根节点的子树，若是能够找到o2节点，则返回当前的遍历祖先节点。

具体步骤

1.遍历二叉树找o1节点，搜索期间将对应的父子节点对存储至map中；
2.找到o1节点后，从o1或o1的祖先节点开始进行搜索查找o2节点；
3.循环遍历，直至找到o2节点，返回当前搜索的子树的根节点。

代码如下：

import java.util.*;
/*
* public class TreeNode {
*   int val = 0;
*   TreeNode left = null;
*   TreeNode right = null;
* }
*/
public class Solution {
/**
* 
* @param root TreeNode类 
* @param o1 int整型 
* @param o2 int整型 
* @return int整型
*/
public int lowestCommonAncestor (TreeNode root, int o1, int o2) {
   // 根节点值为o1或o2直接返回
   if (root.val == o1 || root.val == o2){
       return root.val;
   }
   // 父子节点对
   Map<Integer,TreeNode> map = new HashMap<>();
   // 辅助DFS的数据结构
   Stack<TreeNode> stack = new Stack<>();
   stack.push(root);
   map.put(root.val,root);
   TreeNode node = null;
   while(!stack.isEmpty()){
       node = stack.pop();
       // 找到O1节点，map中存储的是o1节点的所有先驱
       if (node.val == o1){
           break;
       }
       if (node.left != null){
           stack.push(node.left);
           map.put(node.left.val,node);
       }
       if (node.right != null){
           stack.push(node.right);
           map.put(node.right.val,node);
       }
   }
   return findCommonAncestor(map,node,o2);
}
// 从o1以及其先驱中，找出与o2的公共祖先
private int findCommonAncestor(Map<Integer,TreeNode>
                                   map,TreeNode node,int o2){
   while(map.get(node.val) != node){
       TreeNode res = findAnotherNode(map,node,o2);
       if (res != null){
           // 找到最近公共祖先
           return node.val;
       }
       node = map.get(node.val);
   }
   // 返回根节点
   return node.val;
}
// 找o2节点
private TreeNode findAnotherNode(Map<Integer,TreeNode>
                                   map,TreeNode root,int o2){
   Stack<TreeNode> stack = new Stack<>();
   stack.push(root);
   TreeNode n = null;
   TreeNode node = null;
   // DFS
   while(!stack.isEmpty()){
       n = stack.pop();
       // 找到o2节点，返回公共节点
       if (n.val == o2){
           node = n;
           break;
       }
       if (n.left != null){
           stack.push(n.left);
           map.put(n.left.val,n);
       }
       if (n.right != null){
           stack.push(n.right);
           map.put(n.right.val,n);
       }
   }
   return node;
}
}

时间复杂度： $O(n^2)$ ，最坏的情况是，最近公共祖先为根节点，且o2为根节点的右子节点，o1为根节点的左子树的叶子节点，且左子树类似于链表，首先找到o1需要 $O(n-1)$ 即 $O(n)$ ，再依据o1的所有祖先节点寻找o2需要1+2+3+……+n-1，所以时间复杂度为 $O(n^2)$ 。
空间复杂度： $O(n)$ ，最坏情况下为 $O(n)$ 。
方法二

思路
o1，o2，以及公共祖先ancestor的位置关系为以下三种情况：
1.o1，o2在ancestor的左右两侧；
2.o1是祖先，o2在o1的左/右侧；
3.o2是祖先，o1在o2的左/右侧。
故可以通过递归的DFS搜索来查询ancestor。
具体步骤
参考下图的栗子：

代码如下：

import java.util.*;
/*
* public class TreeNode {
*   int val = 0;
*   TreeNode left = null;
*   TreeNode right = null;
* }
*/
public class Solution {
/**
* 
* @param root TreeNode类 
* @param o1 int整型 
* @param o2 int整型 
* @return int整型
*/
public int lowestCommonAncestor (TreeNode root, int o1, int o2) {
   // write code here
   return ancestor(root,o1,o2).val;
}
private TreeNode ancestor(TreeNode root,int o1,int o2){
   // root为空，或者为所找的节点，直接返回
   if (root == null || root.val == o1 || root.val == o2){
       return root;
   }
   // 查找左子树
   TreeNode left = ancestor(root.left,o1,o2);
   // 查找右子树
   TreeNode right = ancestor(root.right,o1,o2);
   // 左子树为空，则全在右子树
   if (left == null){
       return right;
   }
   // 全在左子树
   if (right == null){
       return left;
   }
   // 公共祖先为root
   return root;
}
}

时间复杂度： $O(n)$ ,遍历所有节点；
空间复杂度： $O(n)$ ，递归过程中栈的空间消耗，空间复杂度取决于递归调用的层数，递归调用的层数不会超过较小的二叉树的最大高度，最坏情况下，二叉树的高度等于结点数。

题解 | #在二叉树中找到两个节点的最近公共祖先#

题目

描述

方法一

思路

具体步骤

方法二

思路

具体步骤