题解 | #二叉搜索树的最近公共祖先#

二叉搜索树的最近公共祖先

https://www.nowcoder.com/practice/d9820119321945f588ed6a26f0a6991f

import java.util.*;

/*
 * public class TreeNode {
 *   int val = 0;
 *   TreeNode left = null;
 *   TreeNode right = null;
 *   public TreeNode(int val) {
 *     this.val = val;
 *   }
 * }
 */

public class Solution {
       int lastFather = -1; // 最近祖先
    public int lowestCommonAncestor (TreeNode root, int p, int q) {
        TreeNode currentNode = root;
        while(true){
            lastFather = currentNode.val;
		    // 当p、q有一人到达目的地,旅途结束
            if(p == lastFather || q == lastFather){
                break;
            }
            if(currentNode.val > p){
                if(currentNode.val > q){
				   // p、q的共同目的地:左子树
                    currentNode = currentNode.left;
                }else {
                    // 分别,旅途结束
                    break;
                }
            }else {
                if(currentNode.val < q){
				  // p、q的共同目的地:右子树
                    currentNode = currentNode.right;
                }else {
                    // 分别,旅途结束
                    break;
                }
            }
        }
        return lastFather;
    }
  

}

全部评论

相关推荐

不愿透露姓名的神秘牛友
07-04 14:23
steelhead:你回的有问题,让人感觉你就是来学习的
点赞 评论 收藏
分享
不愿透露姓名的神秘牛友
今天 12:23
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务