题目

描述

• 给定一棵二叉树(保证非空)以及这棵树上的两个节点对应的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;
  }
  }

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

  方法二

  思路

• 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;
  }
  }

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