二叉树的最近公共祖先合集

剑指offer86：在二叉树中查找

public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q){
        if(root==null||root==p||root==q) return root;
        TreeNode left=lowestCommonAncestor(root.left,p,q);
        TreeNode right=lowestCommonAncestor(root.right,p,q);
        if(left==null&&right==null) return null;
        if(left==null) return right;
        if(right==null) return left;
        return root;
    }

思路：可以理解成是利用后序遍历查找二叉树中的p和q，找到就返回结点，没有找到就返回null。

剑指offer68:

方法一：利用二叉搜索树的特性，左子树<根结点<右子树，比较根结点和pq两点大小，确定两点位置。

public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q){
        while((root.val-p.val)*(root.val-q.val)>0) {
            root=root.val 
方法二：同上题
					
										


					

						
欢迎分享，转载请注明来源：内存溢出
原文地址: http://outofmemory.cn/zaji/5713357.html