精华内容
下载资源
问答
  • 给定一个二叉树, 找到该中两个指定节点的最近公共祖先。 百度百科中最近公共祖先的定义为:“对于有根树 T 的两个结点 p、q,最近公共祖先表示为一个结点 x,满足 x 是 p、q 的祖先且 x 的深度尽可能大(一个节点...

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

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

    例如,给定如下二叉树:  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 为不同节点且均存在于给定的二叉树中。

     

    package LeetCode;
    
    
    public class LowestCommonAncestor {
    
        public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
            //判断root为空
            if (root == null) return null;
            //如果有一项相等则进行返回相应的root  就是本身相等下面有节点q也没问题
            // 他会走右子树如果右子树如果右子树有就会向上找公共祖先没有则会返回此处root
            if (root.val == p.val || root.val == q.val) {
                return root;
            }
            //左子树返回的节点(用作后期判断当前节点左右子树是否都含有pq其实就是判断root是否为公共祖先)
            TreeNode left = lowestCommonAncestor(root.left, p, q);
            //右子树返回的节点
            TreeNode right = lowestCommonAncestor(root.right, p, q);
            //用作后期判断当前节点左右子树是否都含有pq其实就是判断root是否为公共祖先
            if (left != null && right != null) {
                return root;
            } else if (left != null) { //向上一级返回不是空的那一项表示有一个达到条件的结果
                return left;
            } else if (right != null) {//同上
                return right;
            } else
                return null;
        }
    }
    

     

    展开全文
  • TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) { if(p->val<root->val and q->val<root->val){ return lowestCommonAncestor(root->left,p,q);...
  • 给定一个二叉搜索, 找到该中两个指定节点的最近公共祖先。 百度百科中最近公共祖先的定义为:“对于有根树 T 的两个结点 p、q,最近公共祖先表示为一个结点 x,满足 x 是 p、q 的祖先且 x 的深度尽可能大(一...

    1.反转字符串

    题目描述:

    编写一个函数,其作用是将输入的字符串反转过来。输入字符串以字符数组 char[] 的形式给出。

    不要给另外的数组分配额外的空间,你必须原地修改输入数组、使用 O(1) 的额外空间解决这一问题。

    你可以假设数组中的所有字符都是 ASCII 码表中的可打印字符。

     

    示例 1:

    输入:["h","e","l","l","o"]
    输出:["o","l","l","e","h"]
    示例 2:

    输入:["H","a","n","n","a","h"]
    输出:["h","a","n","n","a","H"]

    class Solution {
    public:
        void reverseString(vector<char>& s) {
            if(s.size()>0){
                vector<char>::iterator p = s.begin();
                vector<char>::iterator q = s.end()-1;
                while(p<q){
                    char tmp = *p;
                    *p = *q;
                    *q = tmp;
                    p++;
                    q--;
                }
            }
        }
    };

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

    题目描述:

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

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

    例如,给定如下二叉搜索树:  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, 因为根据定义最近公共祖先节点可以为节点本身。

    /**
     * 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 nullptr;
            if(root->val>p->val&&root->val<q->val) return root;
            if(root->val>p->val&&root->val>q->val) return lowestCommonAncestor(root->left,p,q);
            if(root->val<p->val&&root->val<q->val) return lowestCommonAncestor(root->right,p,q);
            return root;
        }
    };

    3.二叉搜索树的第k小元素

    题目描述:

    给定一个二叉搜索树,编写一个函数 kthSmallest 来查找其中第 k 个最小的元素。

    说明:
    你可以假设 k 总是有效的,1 ≤ k ≤ 二叉搜索树元素个数。

    示例 1:

    输入: root = [3,1,4,null,2], k = 1
       3
      / \
     1   4
      \
       2
    输出: 1
    示例 2:

    输入: root = [5,3,6,2,4,null,null,1], k = 3
           5
          / \
         3   6
        / \
       2   4
      /
     1
    输出: 3

    /**
     * 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:
        void inorder(TreeNode* root,vector<int>& path){
            if(root){
                inorder(root->left,path);
                path.push_back(root->val);
                inorder(root->right,path);
            }
        }
        int kthSmallest(TreeNode* root, int k) {
            vector<int> path;
            inorder(root,path);
            return path[k-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:
        void inorder(TreeNode* root,vector<TreeNode*>& path){
            stack<pair<TreeNode*,bool>> s;
            s.push(make_pair(root,false));
            bool visited;
            while(!s.empty()){
                root = s.top().first;
                visited = s.top().second;
                s.pop();
                if(root == NULL) continue;
                if(visited) path.push_back(root);
                else{
                    s.push(make_pair(root->right,false));
                    s.push(make_pair(root,true));
                    s.push(make_pair(root->left,false));
                }
            }
        }
        int kthSmallest(TreeNode* root, int k) {
            vector<TreeNode*> path;
            inorder(root,path);
            return path[k-1]->val;
        }
    };

     

     

     

     

     

     

     

     

     

     

     

     

     

     

     

    展开全文
  • 公共祖先

    2021-04-09 21:43:10
    给定一个二叉搜索, 找到该中两个指定节点的最近公共祖先。 百度百科中最近公共祖先的定义为:“对于有根树 T 的两个结点 p、q,最近公共祖先表示为一个结点 x,满足 x 是 p、q 的祖先且 x 的深度尽可能大(一个...

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

    给定一个二叉搜索树, 找到该树中两个指定节点的最近公共祖先。
    百度百科中最近公共祖先的定义为:“对于有根树 T 的两个结点 p、q,最近公共祖先表示为一个结点 x,满足 x 是 p、q 的祖先且 x 的深度尽可能大(一个节点也可以是它自己的祖先)。”

    例如,给定如下二叉搜索树: 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;说明p,q在当前节点的左子树,向左遍历
    • 当前节点小于p,q说明p,q在当前节点的右子树,向右遍历
    • 否则pq就在当前节点的左右子树两侧,结束
    /**
     * 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) {
            TreeNode ancestor=root;
            while(true){
                if(ancestor.val>p.val&&ancestor.val>q.val){
                    ancestor=ancestor.left;
                }else if(ancestor.val<p.val&&ancestor.val<q.val){
                    ancestor=ancestor.right;
                }else{
                    break;
                }
            }
            return ancestor;
            
        }
    }
    

    时间复杂度O(n): 遍历所有节点
    空间复杂度O(1)

    题目- 236. 二叉树的最近公共祖先

    二叉树的最近公共祖先

    展开全文
  • 1. 二叉搜索的最近公共祖先(力扣:235) 2. 二叉树的最近公共祖先(力扣:236)

    目录


    1. 二叉搜索树的最近公共祖先(力扣:235)
    2. 二叉树的最近公共祖先(力扣:236)

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

    题目

    二叉搜索树的最近公共祖先(力扣:235)

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

    分析

    利用二叉搜索树的特性,左子树节点都小于根节点,右子树节点都大于根节点。

    1. 当两个子节点都大于根节点时,则在右子树查找。
    2. 当两个子节点都小于根节点时,则在左侧查找。
    3. 否则,找到了最近的公共祖先了。

    代码实现

        /**
         * 235. 二叉搜索树的最近公共祖先
         * @param root
         * @param p
         * @param q
         * @return
         */
        public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
            if (root.val > p.val && root.val >q.val){
                return lowestCommonAncestor(root.left, p, q);
            }
            if (root.val < p.val && root.val < q.val){
                return lowestCommonAncestor(root.right, p, q);
            }
            return root;
        }
    

    二叉树的最近公共祖先

    题目

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

    分析

    可以使用递归来实现:

    1. 当root为null或者root等于两个节点中的一个时,返回root节点。
    2. 递归获取左节点和右节点。
    3. 当左节点和右节点都不为空时,代表指定的两个节点都在以root为根节点的树上,这时直接返回root即可。
    4. 如果左节点或右节点中有一个不为null,则返回该节点。
    5. 否则,代表左右节点中都没有要查找的节点,则返回null。

    代码实现

        /**
         * 236. 二叉树的最近公共祖先
         * @param root
         * @param p
         * @param q
         * @return
         */
        public TreeNode lowestCommonAncestor2(TreeNode root, TreeNode p, TreeNode q) {
            if (root == null || root == p || root == q){
                return root;
            }
            TreeNode left = lowestCommonAncestor2(root.left, p, q);
            TreeNode right = lowestCommonAncestor2(root.right, p, q);
            if (left != null && right != null){
                return root;
            }else if (left != null){
                return left;
            }else if (right != null){
                return right;
            }
            return null;
        }
    
    展开全文
  • 235. 二叉搜索的最近公共祖先 236. 二叉树的最近公共祖先
  • 7-11 最近公共祖先

    2021-02-23 21:05:13
    7-11 最近公共祖先 已知结点为互不相等且不等于0的整数。请编写程序找出非空中两个结点的最近公共祖先。例如对于图1(a)所示的t,结点1和2的最近公共祖先是5;结点2和4的最近公共祖先是8。 输入格式: 输入为...
  • 二叉搜索的最近公共祖先 题目链接:剑指 Offer 68 - I. 二叉搜索的最近公共祖先 235. 二叉搜索的最近公共祖先 class Solution { public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode...
  • 235. 二叉搜索的最近公共祖先 给定一个二叉搜索, 找到该中两个指定节点的最近公共祖先。 思路 要记得利用到二叉搜索的性质,当遍历到当前节点的值都比p、q小时,需要右移,当前节点的值比p、q大时,需要左移...
  • 二叉搜索的最近公共祖先 给定一个二叉搜索, 找到该中两个指定节点的最近公共祖先。 最近公共祖先的定义为:“对于有根树 T 的两个结点 p、q,最近公共祖先表示为一个结点 x,满足 x 是 p、q 的祖先且 x 的深度...
  • LeetCode——二叉搜索最近公共祖先 题目描述: 给定一个二叉搜索, 找到该中两个指定节点的最近公共祖先。 百度百科中最近公共祖先的定义为:“对于有根树 T 的两个结点 p、q,最近公共祖先表示为一个结点 x,...
  • leetcode 235 二叉搜索最近公共祖先 题目描述: 给定一个二叉搜索, 找到该中两个指定节点的最近公共祖先。百度百科中最近公共祖先的定义为:“对于有根树 T 的两个结点 p、q,最近公共祖先表示为一个结点 x,...
  • 235. 二叉搜索的最近公共祖先难度简单246给定一个二叉搜索, 找到该中两个指定节点的最近公共祖先。 百度百科中最近公共祖先的定义为:“对于有根树 T 的两个结点 p、q,最近公共祖先表示为一个结点 x,满足 x...
  • 给定一个二叉搜索, 找到该中两个指定节点的最近公共祖先。 百度百科中最近公共祖先的定义为:“对于有根树 T 的两个结点 p、q,最近公共祖先表示为一个结点 x,满足 x 是 p、q 的祖先且 x 的深度尽可能大(一个...
  • 二叉搜索的最近公共祖先
  • 面试题68 - I 二叉搜索的最近公共祖先 题目描述: 给定一个二叉搜索, 找到该中两个指定节点的最近公共祖先。 百度百科中最近公共祖先的定义为:“对于有根树 T 的两个结点 p、q,最近公共祖先表示为一个结点 ...
  • 原题链接:二叉搜索的最近公共祖先 题目:给定一个二叉搜索, 找到该中两个指定节点的最近公共祖先。 百度百科中最近公共祖先的定义为:“对于有根树 T 的两个结点 p、q,最近公共祖先表示为一个结点 x,满足...
  • 目录标题二叉搜索查找最近公共祖先题目思路:根据结点值判断左/右子递归查找二叉树查找最近公共祖先题目思路:对左右子树分别查找最近公共子结点,根据是否找到来返回根结点/左边查找结果/右边查找结果 ...
  • 的最近公共祖先

    2019-04-07 00:49:53
    LCA(Lowest Common Ancestors),即最近公共祖先,是指在有根树中,找出某两个结点u和v最近的公共祖先。 推荐书籍:算法进阶指南 倍增算法(在线) //n结点的,输出任意两个结点间的最小距离 #include<...
  • 给定一个二叉搜索, 找到该中两个指定节点的最近公共祖先。 百度百科中最近公共祖先的定义为:“对于有根树 T 的两个结点 p、q,最近公共祖先表示为一个结点 x,满足 x 是 p、q 的祖先且 x 的深度尽可能大(一个...
  • 235.二叉搜索的最近公共祖先 236.二叉树的最近公共祖先 235.二叉搜索的最近公共祖先 给定一个二叉搜索, 找到该中两个指定节点的最近公共祖先。 百度百科中最近公共祖先的定义为:“对于有根树 T 的两个...
  • 1、二叉搜索的最近公共祖先 输入: root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 8 输出: 6 解释: 节点 2 和节点 8 的最近公共祖先是 6。 输入root为层序遍历的结果,可直接还原完全二叉树 解法:利用上述...
  • 假设在左子树上求的公共祖先L,在右子上求的公共祖先R,之后开始分情况进行讨论: 当L == null & R == null时,说明p和q没有出现在A子树上,返回空 当L == null & R != null时,说明p和q的公共祖先出现在...
  • 235,二叉搜索的最近公共祖先,easy 236,二叉树的最近公共祖先,medium 前序 最近公共祖先的定义为:“对于有根树 T 的两个结点 p、q,最近公共祖先表示为一个结点 x,满足 x 是 p、q 的祖先且 x 的深度尽可能大...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 5,652
精华内容 2,260
关键字:

树公共祖先