常考数据结构与算法:在二叉树中找到两个节点的最近公共祖先

题目描述

给定一棵二叉树以及这棵树上的两个节点 o1 和 o2，请找到 o1 和 o2 的最近公共祖先节点。   假设节点的值都大于0.

 

 比如9，10的最近公共祖先节点是2.

 

   思路:    

   从根节点开始遍历，如果o1和o2中的任一个和root匹配，那么root就是最低公共祖先。 如果都不匹配，则分别递归左、右子树，如果有一个 节点出现在左子树，并且另一个节点出现在右子树，则root就是最低公共祖先.  如果两个节点都出现在左子树，则说明最低公共祖先在左子树中，否则在右子树。

public class LowestCommonAncestor {public static void main(String[] args) {}/**** @param root TreeNode类* @param o1 int整型* @param o2 int整型* @return int整型*/public int lowestCommonAncestor (TreeNode root, int o1, int o2) {//递归的出口if(root==null){return 0;}if(o1==root.val||o2==root.val){return root.val;}//递归调用int left=lowestCommonAncestor(root.left,o1,o2); //左子树int right=lowestCommonAncestor(root.right,o1,o2); //右子树if(left > 0 && right > 0){return root.val;}if (left > 0 )return left;elsereturn right;} }

 

总结

以上是生活随笔为你收集整理的常考数据结构与算法:在二叉树中找到两个节点的最近公共祖先的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。