精华内容
下载资源
问答
  • leetcode题目给定一个二叉搜索树, 找到该树中两个指定节点的最近公共祖先。 例如,给定如下二叉搜索树: root = [6,2,8,0,4,7,9,null,null,3,5] 示例 1: 输入: root = [6,2,8,0,4,7,9,null,null,3,5],

    二叉搜索树查找最近公共祖先

    题目

    leetcode题目给定一个二叉搜索树, 找到该树中两个指定节点的最近公共祖先。

    例如,给定如下二叉搜索树: root = [6,2,8,0,4,7,9,null,null,3,5]
    在这里插入图片描述
    示例 1:

    输入: root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 8
    输出: 6 
    解释: 节点 2 和节点 8 的最近公共祖先是 6。
    

    示例 2:

    输入: root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 4
    输出: 2
    解释: 节点 2 和节点 4 的最近公共祖先是 2, 因为根据定义最近公共祖先节点可以为节点本身。
    

    说明:

    所有节点的值都是唯一的。
    p、q 为不同节点且均存在于给定的二叉搜索树中。
    

    思路:根据结点值判断左/右子树递归查找

    1. 如果两个结点都在右侧子树,则将问题转换为在右侧子树查找
    2. 如果两个结点都在左侧子树,则将问题转换为在左侧子树查找
    3. 否则,当前根结点就是我们要找的最近公共祖先(要么两个结点一左一右,要么两个结点中的一个其实就是根结点)
    • 时间复杂度:O(n)
    • 空间复杂度:O(1)
    /**
     * Definition for a binary tree node.
     * struct TreeNode {
     *     int val;
     *     TreeNode *left;
     *     TreeNode *right;
     *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
     * };
     */
    class Solution {
    public:
        TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
            if(root==NULL){
                return root;
            }
            if(root->val > p->val && root->val > q->val){
                return lowestCommonAncestor(root->left, p, q);
            }else if(root->val < p->val && root->val < q->val){
                return lowestCommonAncestor(root->right, p, q);
            }else{
                return root;
            }
        }
    };
    

    或者

    /**
     * Definition for a binary tree node.
     * struct TreeNode {
     *     int val;
     *     TreeNode *left;
     *     TreeNode *right;
     *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
     * };
     */
    class Solution {
    public:
        TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
            while(root!=NULL){
                if(root->val > p->val && root->val > q->val){
                    root = root->left;
                }else if(root->val < p->val && root->val < q->val){
                    root = root->right;
                }else{
                    break;
                }
            }
            return root;
        }
    };
    

    二叉树查找最近公共祖先

    题目

    leetcode题目给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。
    例如,给定如下二叉树: root = [3,5,1,6,2,0,8,null,null,7,4]
    在这里插入图片描述
    示例 1:

    输入: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 1
    输出: 3
    解释: 节点 5 和节点 1 的最近公共祖先是节点 3。
    

    示例 2:

    输入: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 4
    输出: 5
    解释: 节点 5 和节点 4 的最近公共祖先是节点 5。因为根据定义最近公共祖先节点可以为节点本身。
    

    说明:

    所有节点的值都是唯一的。
    p、q 为不同节点且均存在于给定的二叉树中。
    

    思路:对左右子树分别查找最近公共子结点,根据是否找到来返回根结点/左边查找结果/右边查找结果

    1. 当前根结点为空,返回空
    2. 两个结点之一是当前根结点,返回根结点
    3. 对左子树进行最近公共子结点的查找
    4. 对右子树进行最近公共子结点的查找
    5. 如果在左右子树都找到了,说明结点分布在两边,那当前根结点就是最近公共祖先;否则如果只在左子树找到了,那就直接返回在左子树找到的结果;否则如果只在右子树找到了,那就直接返回在右子树找到的结果
    • 时间复杂度O(n):其中n是二叉树的节点数,二叉树的所有节点有且只会被访问一次
    • 空间复杂度O(n):其中n是二叉树的节点数,二叉树的所有节点有且只会被访问一次,递归调用的栈深度取决于二叉树的高度,二叉树最坏情况下为一条链,此时高度为n
    /**
     * Definition for a binary tree node.
     * struct TreeNode {
     *     int val;
     *     TreeNode *left;
     *     TreeNode *right;
     *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
     * };
     */
    class Solution {
    public:
        TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
            //递归终止条件:
            //1、根结点为空,则返回空
            if( root==NULL )
                return NULL;
            //2、p或q就是根结点,则返回根结点
            if( root==p || root==q ){
                return root;
            }
            //往左子树找最近公共祖先
            TreeNode* l = lowestCommonAncestor(root->left, p, q);
            //往右子树找最近公共祖先
            TreeNode* r = lowestCommonAncestor(root->right, p, q);
            if( l!=NULL && r!=NULL){ //左右子树都找到了最近公共祖先,说明结点分布在根结点两边,那当前根结点就是最近公共祖先
                return root;
            }else if( l!=NULL ){ //只有左子树找到了,直接返回结果
                return l;
            }else{ //只有右子树找到了,也直接返回结果
                return r;
            }
        }
    };
    
    展开全文
  • 2、怎样判断节点p和节点q的最近公共祖先呢? (1)、某个节点是节点p和节点q的公共祖先:如果找到一个节点,发现左子树出现节点p,右子树出现节点q。或者左子树出现节点q,右子树出现节点p,则该节点就是节点p和节点q...

    在这里插入图片描述

    思路:

    如何从底向上遍历?
    遍历整棵树,还是遍历局部树?
    如何把结果传到根节点的?

    1、利用回溯实现自底向上搜索,查找最近公共祖先。
    后序遍历就是一个回溯过程,最先处理的节点一定是叶子节点。

    2、怎样判断节点p和节点q的最近公共祖先呢?
    (1)、某个节点是节点p和节点q的公共祖先:如果找到一个节点,发现左子树出现节点p,右子树出现节点q。或者左子树出现节点q,右子树出现节点p,则该节点就是节点p和节点q的最近公共祖先。
    (2)节点p或节点q是节点p和节点q的公共祖先:某一个节点左/右子树出现p/q,右/左子树为空

    递归法

    1、确定递归函数的参数和返回值:

    需要递归函数的返回值来告诉我们是否找到了节点p和节点q,那么返回值类型理应是bool型。

    但是我们如果找到了最近公共祖先,还要返回最近公共祖先这个节点。

    怎么办呢,那就利用题目所给的TreeNode* ,如果遇到了p或者q,就把p或者q返回,代表找到了(true)。如果没遇到就返回空,代表没找到(false)

    TreeNode* lowestCommonAncestor(TreeNode* root,TreeNode* p,TreeNode* q);
    

    2、确定终止条件
    如果找到了节点p或者q,或者遇到了空节点,就返回

    if(root==p||root==q||root==NULL) return NULL;
    

    3、确定单层递归的逻辑

    TreeNode* left = lowestCommonAncestor(root->left, p, q);
    TreeNode* right = lowestCommonAncestor(root->right, p, q);
    
    if (left == NULL && right != NULL) return right;
    else if (left != NULL && right == NULL) return left;
    else { // (left == NULL && right == NULL)
    return NULL;
    }
    

    在这里插入图片描述
    完整递归代码

    class Solution {
    public:
       TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        if (root == q || root == p || root == NULL) return root;
    
        TreeNode* left = lowestCommonAncestor(root->left, p, q);
        TreeNode* right = lowestCommonAncestor(root->right, p, q);
    
        if (left != NULL && right != NULL) return root; //1
    
        if (left == NULL && right != NULL) return right;//2
    
        else if (left != NULL && right == NULL) return left;//3,左边不为空,右边为空,如果先遇到p,说明q一定在p下面,两者公共祖先一定是先遇到的那个。
            else { // (left == NULL && right == NULL)
              return NULL;//4
            }
       }
    };
    

    总结

    1、首先求最近公共祖先,需要从底向上遍历,那么⼆叉树,只能通过后序遍历(即:回溯)实现从底向上的遍历⽅式。

    2、然后,我们要根据节点是否是公共祖先的评判标准 ,也就是如果找到⼀个节点,发现左⼦树出现结点p,右⼦树出现节点q,或者 左⼦树出现结点q,右⼦树出现节点p,那么该节点就是节点p和q的最近公共祖先,得出递归函数必须要有返回值用来判断节点左右子树情况,返回最近公共节点。
    一般我们会想既然递归函数有返回值,则是单边搜索,于是就用了1的用法
    但我们发现了在这种情况是无法完成任务的,因为存在两种情况使我们无法判断要返回哪个节点,即左右子树都不为空和左右子树有一个为空。

    所以我们想出了用法2,即全树搜索,总的来看是对返回值根据不同场合进行了不同的处理。

    1、

    if (递归函数(root->left)) return ;
    if (递归函数(root->right)) return ;
    

    2、

    left = 递归函数(root->left);
    right = 递归函数(root->right);
    left与right的逻辑处理;
    

    3、所以在回溯的过程中,必然要遍历整棵⼆叉树,即使已经找到结果了,依然要把其他节点遍历完,因为要使⽤递归函数的返回值(也就是代码中的left和right)做逻辑判断。

    4、 要理解如果返回值left为空, right不为空为什么要返回right,为什么可以⽤返回right传给上⼀层结果。

    (1)如果当前节点是p或q,则返回p或q,为特殊情况之一,在终止条件得到解决。

    (2)当前节点左子树p/q,右子树q/p,为一般情况,在单层处理逻辑中解决。

    (3)当前节点左子树为空,右子树为q/p,或者左子树为q/p,右子树为空,为特殊情况之二,也在单层处理逻辑中解决。

    展开全文
  • 一、最近公共祖先的定义 对于有根树 T 的两个结点 p、q,最近公共祖先表示为一个结点 x,满足 x 是 p、q 的祖先且 x 的深度...三、通过分析,用代码找出二叉树中两节点的最近公共祖先 从根节点出发,同时查找给定的两个

    一、最近公共祖先的定义

    对于有根树 T 的两个结点 p、q,最近公共祖先表示为一个结点 x,满足 x 是 p、q 的祖先且 x 的深度尽可能大(一个节点也可以是它自己的祖先);

    二、举例说明
    在这里插入图片描述
    在此树中,两个节点的公共祖先:

    两个节点 公共祖先 最近公共祖先
    6 和 7 5, 3 5
    7 和 8 3 3
    4 和 2 2, 5, 3 2
    6 和 2 5, 3 5
    4 和 6 5, 3 5

    三、通过分析,用代码找出二叉树中两节点的最近公共祖先

    从根节点出发,同时查找给定的两个节点

    查找之后可能出现的情况有:

    1. 从该节点出发,两个节点都没有找到(该节点不是公共祖先)
    2. 从该节点出发,只找到其中一个节点(该节点只是这个节点的祖先,不是公共祖先)
    3. 从该节点出发,两个节点都找到了,该节点就是公共祖先
      a).如果找到的两个目标节点分散在三个位置(根节点,左子树,右子树)的两处,此时该节点就是最近公共祖先
      b).如果两目标节点同时出现在该节点的左子树或是右子树中,此时该节点一定不是最近公共祖先

    代码如下

    	// 用来保存最近公共节点
        public TreeNode lca = null;
        public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
            if (root == null) {
                return null;
            }
            findNode(root, p, q);
            return lca;
        }
    
        // [约定] 如果在 root 中能找到 p 或 q ,就返回 true,否则就返回 false
        private boolean findNode(TreeNode root, TreeNode p, TreeNode q) {
            if (root == null) {
                return false;
            }
            // 后续遍历
            int left = findNode(root.left, p, q) ? 1 : 0;
            int right = findNode(root.right, p, q) ? 1 : 0;
            // 访问根节点
            int mid = (root == p || root == q)? 1 : 0;
            if (left + right + mid == 2) {
                lca = root;
            }
            return (left + right + mid) > 0;
        }
    

    left, right,mid 取值只有 1, 0 两种情况
    当三者相加值为 2 的时候,意味着一定是三个变量中两个是 1 ,一个是0;至于谁是 1, 谁是 0,不做要求
    举例:假设 p 和 q 同时出现在左子树中,left = 1,right 和 mid = 0,和不为 2;
    假设 p 和 q 同时出现在左子树中,right = 1, left 和 mid = 0, 和不为 2;
    假设 p 和 q 分别出现在左子树和右子树中, left = 1,right = 1, mid = 0,和为 2;
    ……
    当 p 和 q 分别在(左子树,右子树,根节点)其中两个位置时,此当前根节点就是最近公共节点

    展开全文
  • * 去以root为根节点的二叉树查找p、q的最近公共祖先 * ① 如果p、q同时存在于这棵二叉树中,就能成功返回它们的最近公共祖先 * ② 如果p、q都不存在于这棵二叉树中,返回null * ③ 如果只有p存在于这棵二叉树中...
     * 去以root为根节点的二叉树中查找p、q的最近公共祖先
     * ① 如果p、q同时存在于这棵二叉树中,就能成功返回它们的最近公共祖先
     * ② 如果p、q都不存在于这棵二叉树中,返回null
     * ③ 如果只有p存在于这棵二叉树中,返回p
     * ④ 如果只有q存在于这棵二叉树中,返回q
    

    下面的这种写法是错误的

    /**
     * Definition for a binary tree node.
     * public class TreeNode {
     *     int val;
     *     TreeNode left;
     *     TreeNode right;
     *     TreeNode(int x) { val = x; }
     * }
     */
    class Solution {
        public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
            if (root == null || root == p || root == q) return root;
            // 去以root.left为根节点的二叉树中查找p、q的最近公共祖先
            TreeNode left = lowestCommonAncestor(root.left, p, q);
            // 去以root.right为根节点的二叉树中查找p、q的最近公共祖先
            TreeNode right = lowestCommonAncestor(root.right, p, q);
            if (left != null && right == null) {
                return left;
            }
            if (left == null && right != null) {
                return right;
            }
            return root;        
        }
    }
    

    在这里插入图片描述



    正确的解法如下:

    /**
     * Definition for a binary tree node.
     * public class TreeNode {
     *     int val;
     *     TreeNode left;
     *     TreeNode right;
     *     TreeNode(int x) { val = x; }
     * }
     */
    class Solution {
        public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
            if (root == null || root == p || root == q) return root;
            // 去以root.left为根节点的二叉树中查找p、q的最近公共祖先
            TreeNode left = lowestCommonAncestor(root.left, p, q);
            // 去以root.right为根节点的二叉树中查找p、q的最近公共祖先
            TreeNode right = lowestCommonAncestor(root.right, p, q);
            if (left != null && right != null) return root;
            return (left != null) ? left : right;      
        }
    }
    

    在这里插入图片描述

    展开全文
  • 面试题68 - II 二叉树的最近公共祖先 给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。 百度百科中最近公共祖先的定义为:“对于有根树 T 的两个结点 p、q,最近公共祖先表示为一个结点 x,满足 x 是 p、q ...
  • 给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。 百度百科中最近公共祖先的定义为:“对于有根树 T 的两个结点 p、q,最近公共祖先表示为一个结点 x,满足 x 是 p、q 的祖先且 x 的深度尽可能大(一个节点...
  • LCA(LCA最近公共祖先)问题,和之前那个的二叉搜索树的最近公共祖先区别是这是普通的二叉树 注意p,q必然存在树内, 且所有节点的值唯一!!! 递归思想, 对以root为根的(子)树进行查找p和q, 如果root == null || p || q...
  • 二叉树的最近公共祖先 题目描述: 思路解析: 1、查找:递归遍历,查找两个目标结点的路径,并且将路径存放进栈内 2、栈的裁剪:将两个栈按照小的栈进行裁剪,变成等长 3、查找公共祖先 图示: /** * Definition...
  • 给定一个二叉树, 找到该树中两个指定节点的最近公共祖先 百度百科中最近公共祖先的定义为:对于有根树 T 的两个节点 p、q,最近公共祖先表示为一个节点 x,满足 x 是 p、q 的祖先且 x 的深度尽可能大(一个节点也...
  • 题目:...判断节点是不是最近的公共祖先:一个节点左右子树分别出现p和q,或者节点是p或者q,该节点左子树或者右子树出现p或者q;
  • 做题目前随便说点 树是一种抽象数据类型,一种具有树结构形式的数据... 二叉树的最近公共祖先 给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。 百度百科中最近公共祖先的定义为:“对于有根树 T 的两...
  • 递归实现最近公共祖先,...有两种情况,1.p、q在同一条路径上,所以需要找到了p或者q继续向下查找,找到了了最近公共祖先就是这个。2.p,q在两条支路上,那么最近公共祖先的左右子树各包含pq。 /** * De...
  • 二叉搜索树的最近公共祖先 剑指 Offer 68 - I. 二叉搜索树的最近公共祖先 思路 求二叉搜索树中的两个节点p,q的最近公共祖先的思路比较简单: ①如果遍历到的节点node的值在p节点的值和q节点的值之间,则说明p,q...
  • 二叉树的最近公共祖先LCA

    千次阅读 2017-08-22 18:10:58
    二叉树是个二叉查找树,且root和两个节点值(a, b)已知。 如果该二叉树是二叉查找树,那么求解LCA十分简单。 基本思想为:从树根开始,该节点值为t, 如果t大于t1和t2,说明t1和t2都位于t左侧,所以...
  • 二叉树的最近公共祖先 思路 在左、右子树中分别查找是否包含p或q: 如果以下两种情况(左子树包含p,右子树包含q/左子树包含q,右子树包含p),那么此时的根节点就是最近公共祖先 如果左子树包含p和q,那么到root...
  • postTraverse函数作用是找到根节点到指定结点路径,找根节点到指定结点路径使用后序遍历,但是需要注意是,当root结点是其父节点左孩子,并且root已经是需要查找的节点或者需要查找的节点已经找时候,就...
  • 第一种根节点与其中一个节点值一致,则公共祖先即为根节点,比如待查找的节点为3、2,则必然为3 第二种待查找的节点为2、7,即2个节点均在左子树中,则根节点必然在左子树中,具体求取思路为: 先判定2、7 不与根...
  • 力扣.236 前提条件:p,q必然存在树内, 且所有节点值唯一!... 表示对于当前树的查找已经完毕, 否则对左右子树进行查找, 根据左右子树返回值判断: 1. 左右子树返回值都不为null, 由于值唯一左...
  • 递归去遍历左右子树是否包含要查找的节点 /** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode(int x) : val(x), left(NULL), rig....
  • 递归思路 首先判断当前节点是否命中(if(rootp || rootq)),命中则返回;...或者公共祖先在当前节点子节点上; struct TreeNode { int val; TreeNode* left; TreeNode* right; TreeNode(int x) : v
  • 这是剑指Offer的最后一道题,本质是二叉树的后序遍历(非递归)。牢牢记住二叉树的后序遍历以非递归形式遍历到某一节点时,辅助栈内保存的元素即为根节点到该节点的路径。 知道了上面的性质后,我们就可以利用这两个...
  • 给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。 思路 我们首先能想到的是, 当以root为根节点进行查找时,如果p或者q刚好等于root,那么p和q的最近公共祖先就是root。 那如果p或者q都不等于root怎么办呢...
  • 递归思想, 对以root为根(子)树进行查找p和q, 如果root == null || p || q 直接返回root表示对于当前树的查找已经完毕, 否则对左右子树进行查找, 根据左右子树返回值判断: 左右子树返回值都不为null, 由于值...
  • 解题思路: ...2.递归查找其左右子树; 3.根据左右子树结果,找到规则即可。 具体代码如下: # Definition for a binary tree node. # class TreeNode: # def __init__(self, x): # self.val = x # ...
  • 如图所示,若要查找节点4和节点5的最近公共祖先。从图中我们可以看到最近的公共祖先为节点2,那么怎样才能找到这个节点2呢? 思路: 从根节点1到节点4和节点5的路径分别为{1,2,4}和{1,2,5},可以发现2节点是两个..

空空如也

空空如也

1 2 3 4 5 ... 8
收藏数 153
精华内容 61
关键字:

查找二叉树的最近公共祖先