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

缺乏、安全感 2022-03-10 13:56 206阅读 0赞

题目：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM5MDgzMDA0_size_16_color_FFFFFF_t_70]

解题思路：递归，二叉搜索树两个点

二叉搜索树：二叉查找树，主要特点是，根节点比左孩子大，比右孩子小，即左小右大根中间。

/**
     * Definition for a binary tree node.
     * function TreeNode(val) {
     *     this.val = val;
     *     this.left = this.right = null;
     * }
     */
    /**
     * @param {TreeNode} root
     * @param {TreeNode} p
     * @param {TreeNode} q
     * @return {TreeNode}
     */
    var lowestCommonAncestor = function(root, p, q) {
        var res;
        result(root, p, q);
    
        function result(root, p, q) {
            if ((root.val - p.val) * (root.val - q.val) <=0) {
                res = root
            } else if (root.val < p.val && root.val < q.val) {
                result(root.right, p, q)
            } else result(root.left, p, q)
        }
    
        return res;
    };

当然最初的思路不是我的，这种比较好理解。

注：注意第二种特殊情况，所以在第一个if判断中进行处理。  
![在这里插入图片描述][20190311114251644.jpg]  
我最初的思路是进行两次遍历，比较麻烦并且难理解，但是也可以ac。（ps:第一天）

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM5MDgzMDA0_size_16_color_FFFFFF_t_70]: /images/20220310/b60f15320ea14ccaa82b345e1e57d2f7.png
[20190311114251644.jpg]: /images/20220310/4b1c7b0489af40fd8c2480a311a21c82.png

发表评论取消回复

表情：

评论列表（有 0 条评论，206人围观）

还没有评论，来说两句吧...

相关阅读

相关 LeetCode235.二叉树搜索树的最近公共祖先

解题思路若节点p，q都小于当前搜索节点的值，则搜索当前搜索节点的左子树。若节点p，q都大于当前搜索节点的值，则搜索当前搜索节点的右子树。直到p小于当前搜索节点的

以你之姓@/ 2023年09月25日 21:31/ 0 赞/ 2 阅读

相关 235. 二叉搜索树的最近公共祖先

参考： [剑指 Offer 68 - I. 二叉搜索树的最近公共祖先][Offer 68 - I.] [Offer 68 - I.]: https://blog.cs

淩亂°似流年/ 2022年12月11日 15:30/ 0 赞/ 127 阅读

相关【leetcode.235】二叉搜索树的最近公共祖先

一、题目描述给定一个二叉搜索树, 找到该树中两个指定节点的最近公共祖先。百度百科中最近公共祖先的定义为：“对于有根树 T 的两个结点 p、q，最近公共祖先表示为一个

￡神魔★判官ぃ/ 2022年12月10日 15:54/ 0 赞/ 149 阅读

相关 leetcode---235. 二叉搜索树的最近公共祖先（最近公共祖先）

给定一个二叉搜索树, 找到该树中两个指定节点的最近公共祖先。百度百科中最近公共祖先的定义为：“对于有根树 T 的两个结点 p、q，最近公共祖先表示为一个结点 x，满足 x

女爷i/ 2022年11月28日 00:42/ 0 赞/ 139 阅读

相关【leetcode235】二叉搜索树的最近公共祖先

题目描述给定一个二叉搜索树, 找到该树中两个指定节点的最近公共祖先。说明: 所有节点的值都是唯一的。 p、q 为不同节点且均存在于给定的二叉搜索树中。

迈不过友情╰/ 2022年11月16日 15:22/ 0 赞/ 124 阅读

相关 235. 二叉搜索树的最近公共祖先

> 给定一个二叉搜索树, 找到该树中两个指定节点的最近公共祖先。（一个节点也可以是它自己的祖先） > > ![watermark_type_ZmFuZ3poZW5naGVpd

﹏ヽ暗。殇╰゛Y/ 2022年10月08日 02:25/ 0 赞/ 170 阅读

相关 235. 二叉搜索树的最近公共祖先

235. 二叉搜索树的最近公共祖先 \\\\题目给定如下二叉搜索树: root = \[6,2,8,0,4,7,9,null,null,3,5\] ___

矫情吗；*/ 2022年05月09日 01:10/ 0 赞/ 140 阅读

相关 235-二叉搜索树的最近公共祖先

题目： ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmN

缺乏、安全感/ 2022年03月10日 13:56/ 0 赞/ 207 阅读

相关 leetcode:235. 二叉搜索树的最近公共祖先

题目: 给定一个二叉搜索树, 找到该树中两个指定节点的最近公共祖先。百度百科中最近公共祖先的定义为：“对于有根树 T 的两个结点 p、q，最近公共祖先表示为一个结点

矫情吗；*/ 2022年03月02日 03:36/ 0 赞/ 177 阅读

相关 235. 二叉搜索树的最近公共祖先

给定一个二叉搜索树, 找到该树中两个指定节点的最近公共祖先。 [百度百科][Link 1]中最近公共祖先的定义为：“对于有根树 T 的两个结点 p、q，最近公共祖先表示为一个

骑猪看日落/ 2021年11月04日 13:44/ 0 赞/ 265 阅读