首页 > 其他分享 >LeetCode 236_ 二叉树的最近公共祖先

LeetCode 236_ 二叉树的最近公共祖先

时间:2023-06-02 14:45:04浏览次数:48  
标签:path2 path1 TreeNode dfs 二叉树 path 236 root LeetCode

class Solution {
public:
    vector<TreeNode*> path1,path2;
    bool dfs(TreeNode* root,TreeNode* p,vector<TreeNode*>& path)
    {
        if(!root)   return false;
        if(root==p||dfs(root->left,p,path)||dfs(root->right,p,path))
        {
            path.push_back(root);
            return true;
        }
        return false;
    }
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        dfs(root,p,path1);
        dfs(root,q,path2);
        reverse(path1.begin(),path1.end());
        reverse(path2.begin(),path2.end());
        TreeNode* res;
        for(int i=0;i<path1.size()&&i<path2.size();i++)
            if(path1[i]==path2[i])   res=path2[i];
        return res;
    }
};

标签:path2,path1,TreeNode,dfs,二叉树,path,236,root,LeetCode
From: https://www.cnblogs.com/tangxibomb/p/17451709.html

相关文章

  • LeetCode235. 二叉搜索树的最近公共祖先
    classSolution{public:TreeNode*lowestCommonAncestor(TreeNode*root,TreeNode*p,TreeNode*q){if(p->val<root->val&&q->val<root->val)returnlowestCommonAncestor(root->left,p,q);if(p->v......
  • 剑指 Offer II 048. 序列化与反序列化二叉树
    题目链接:剑指OfferII048.序列化与反序列化二叉树方法:先序遍历(dfs)解题思路 在先序遍历过程中,节点值之间通过空格隔开,好利于后续反序列化过程中获取值。代码classCodec{public://Encodesatreetoasinglestring.stringserialize(TreeNode*root){......
  • leetcode 1341 电影评分
    leetcode1341 电影评分(selectu1.nameasresultsfromUsersu1leftjoin(selectmr1.user_id,count(mr1.rating)asc1fromMovieRatingasmr1groupbymr1.user_idhavingc1=(selectmax(p.c2)fromUsersasu2......
  • leetcode 65. 有效数字 66. 寻找两个正序数组的中位数
    leetcode65.有效数字66.寻找两个正序数组的中位数65.有效数字难度困难295有效数字(按顺序)可以分成以下几个部分:一个小数或者整数(可选)一个'e'或'E',后面跟着一个整数小数(按顺序)可以分成以下几个部分:(可选)一个符号字符('+'或'-')下述格式之一:至少一位数字,后面跟着一个......
  • 图解LeetCode——98. 验证二叉搜索树
    一、题目给你一个二叉树的根节点root,判断其是否是一个有效的二叉搜索树。有效二叉搜索树定义如下:节点的左子树只包含小于当前节点的数。节点的右子树只包含大于当前节点的数。所有左子树和右子树自身必须也是二叉搜索树。二、示例2.1>示例1:【输入】root=[......
  • LeetCode/叶值的最小代价生成树
    给你一个正整数数组 arr,考虑所有满足以下条件的二叉树:每个节点都有0个或是2个子节点。数组 arr 中的值与树的中序遍历中每个叶节点的值一一对应。每个非叶节点的值等于其左子树和右子树中叶节点的最大值的乘积。在所有这样的二叉树中,返回每个非叶节点的值的最小可能总......
  • LeetCode 96.不同的二叉搜索树
    1.题目:给你一个整数n,求恰由n个节点组成且节点值从1到n互不相同的二叉搜索树有多少种?返回满足题意的二叉搜索树的种数。示例1:输入:n=3输出:5示例2:输入:n=1输出:1来源:力扣(LeetCode)链接:https://leetcode.cn/problems/unique-binary-search-trees著作权归领扣网络所有......
  • LeetCode 343.整数拆分
    1.题目:给定一个正整数 n ,将其拆分为k个正整数的和( k>=2 ),并使这些整数的乘积最大化。返回你可以获得的最大乘积 。示例1:输入:n=2输出:1解释:2=1+1,1×1=1。示例 2:输入:n=10输出:36解释:10=3+3+4,3× 3× 4=36。来源:力扣(LeetCo......
  • POJ2369 置换群
    题目:http://poj.org/problem?id=2369题意:给定一个序列,问需要最少需要置换多少次才能变为有序序列.分析:对于每一位,算出最少的置换到自己应该的数字。每一位都有这样的数字,取最小公倍数就可以。#include<iostream>#include<string.h>#include<stdio.h>usingnamespacestd......
  • 图解LeetCode——102. 二叉树的层序遍历
    一、题目给你二叉树的根节点root,返回其节点值的层序遍历。(即逐层地,从左到右访问所有节点)。二、示例2.1>示例1:【输入】root=[3,9,20,null,null,15,7]【输出】[[3],[9,20],[15,7]]2.2>示例2:【输入】root=[1]【输出】[[1]]2.3>示例3:【输入】root=[]......