当前位置 : 首页 » 文章分类 :  算法  »  LeetCode.235.Lowest Common Ancestor of BST BST的最近公共祖先

LeetCode.235.Lowest Common Ancestor of BST BST的最近公共祖先

题目描述

235 Lowest Common Ancestor of a Binary Search Tree
https://leetcode-cn.com/problems/lowest-common-ancestor-of-a-binary-search-tree/

Given a binary search tree (BST), find the lowest common ancestor (LCA) of two given nodes in the BST.

According to the definition of LCA on Wikipedia: “The lowest common ancestor is defined between two nodes p and q as the lowest node in T that has both p and q as descendants (where we allow a node to be a descendant of itself).”

Given binary search tree:  root = [6,2,8,0,4,7,9,null,null,3,5]


BST

Example 1:

Input: root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 8
Output: 6
Explanation: The LCA of nodes 2 and 8 is 6.

Example 2:

Input: root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 4
Output: 2
Explanation: The LCA of nodes 2 and 4 is 2, since a node can be a descendant of itself according to the LCA definition.

Note:

  • All of the nodes’ values will be unique.
  • p and q are different and both values will exist in the BST.

相似题目

LeetCode.235.Lowest Common Ancestor of BST BST的最近公共祖先
LeetCode.236.Lowest Common Ancestor of a Binary Tree 二叉树的最近公共祖先


解题过程

做这道题的时候没注意到是 BST 树,没用到 BST 的性质,写成了通用的二叉树最低公共祖先的判断方法,专门写了个判断 root 中是否包含 p,q 的方法 containNodes,每次递归过程中加了一次遍历,时间复杂度为 O(n^2),但还是通过了。

其实可以利用 BST 的性质,左子树所有结点值都小于根,右子树所有结点值都大于根,直接把 p,q 的值和 root 比较,然后递归的在左右子树中找最近公共祖先,如果 p,q 一个比 root 小一个比 root 大,则 root 就是 p,q 的最近公共祖先,时间复杂度为O(n)

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

// 非递归先序遍历,判断root中是否包含p和q
public boolean containNodes(TreeNode root, TreeNode p, TreeNode q) {
    if (null == root) {
        return false;
    }
    boolean hasP = false;
    boolean hasQ = false;
    Deque<TreeNode> stack = new LinkedList<>();
    stack.push(root);
    TreeNode cur = root;
    while (!stack.isEmpty() || null != cur) {
        while (null != cur) {
            hasP = cur == p || hasP;
            hasQ = cur == q || hasQ;
            cur = cur.left;
            if (null != cur) {
                stack.push(cur);
            }
        }
        cur = stack.pop();
        if (null != cur.right) {
            stack.push(cur.right);
        }
        cur = cur.right;
    }
    return hasP && hasQ;
}

GitHub代码

algorithms/leetcode/leetcode/_235_LowestCommonAncestorOfBST.java
https://github.com/masikkk/algorithms/blob/master/leetcode/leetcode/_235_LowestCommonAncestorOfBST.java


上一篇 LeetCode.236.Lowest Common Ancestor of a Binary Tree 二叉树的最近公共祖先

下一篇 LeetCode.226.Invert Binary Tree 反转二叉树

阅读
评论
607
阅读预计3分钟
创建日期 2020-01-27
修改日期 2020-01-27
类别

页面信息

location:
protocol:
host:
hostname:
origin:
pathname:
href:
document:
referrer:
navigator:
platform:
userAgent:

评论