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

236. 二叉树的最近公共祖先c

时间:2024-03-14 19:33:51浏览次数:27  
标签:right TreeNode struct 祖先 二叉树 return 236 root left

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     struct TreeNode *left;
 *     struct TreeNode *right;
 * };
 */
struct TreeNode* lowestCommonAncestor(struct TreeNode* root, struct TreeNode* p, struct TreeNode* q) {
    if(!root) return NULL;
    if(root==p||root==q) return root;
    struct TreeNode* left=lowestCommonAncestor(root->left,p,q);
    struct TreeNode* right=lowestCommonAncestor(root->right,p,q);
    if(left==p&&right==q||left==q&&right==p) return root;
    if(left!=p&&left!=q && left) return left;
    if(right&&right!=q&&right!=p) return right;
    if(left==p||left==q) return left;
    if(right==p||right==q) return right;
    return NULL;
}

结果:

标签:right,TreeNode,struct,祖先,二叉树,return,236,root,left
From: https://www.cnblogs.com/llllmz/p/18073747

相关文章

  • leedcode-完全二叉树的节点个数
    自己写的,使用广度优先BFS,迭代:classSolution:defcountNodes(self,root:Optional[TreeNode])->int:#如果根节点为空,则树中节点数为0ifnotroot:return0#初始化队列,并将根节点放入队列中queue=[root]......
  • 洛谷题单指南-二叉树-P5076 【深基16.例7】普通二叉树(简化版)
    原题链接:https://www.luogu.com.cn/problem/P5076题意解读:此题本质上是要实现一个二叉搜索树的功能。解题思路:从数据规模10^4来看,只要复杂度在n^2范围内基本上是可以通过的,下面给出两种做法:1、有序数组法对应5个操作的实现逻辑如下:操作一:查x的排名。直接通过二分查找>=x的第......
  • 617. 合并二叉树c
    /***Definitionforabinarytreenode.*structTreeNode{*intval;*structTreeNode*left;*structTreeNode*right;*};*/structTreeNode*mergeTrees(structTreeNode*root1,structTreeNode*root2){if(!root1&&!roo......
  • 257. 二叉树的所有路径c
    /***Definitionforabinarytreenode.*structTreeNode{*intval;*structTreeNode*left;*structTreeNode*right;*};*//***Note:Thereturnedarraymustbemalloced,assumecallercallsfree().*/chartemp[200]={0};v......
  • 洛谷题单指南-二叉树-P4913 【深基16.例3】二叉树深度
    原题链接:https://www.luogu.com.cn/problem/P4913题意解读:计算二叉树的深度解题思路:首先介绍二叉树的存储方式,对于本题,直接用数组模拟,数组的下标即节点号structnode{intl,r;}tree[N];tree[i].l存的是节点i的左子结点,tree[i].r存的是节点i的右子节点。计算深度至......
  • 【BFS二叉树】113路径总和II
    113路径总和II给你二叉树的根节点root和一个整数目标和targetSum,找出所有从根节点到叶子节点路径总和等于给定目标和的路径。思路:题目最终输出的是路径,因此用BFS遍历的时候,需要记录走到每个节点的路径;又因为路径和是要等于某个目标值的,因此也需要记录目标和。⇒......
  • 数据结构之树(Topk问题, 链式二叉树)
    一.topk问题取N个数中最大(小)的前k个值,N远大于k这道题可以用堆的方法来解决,首先取这N个数的前k个值,用它们建堆时间复杂度O(k)之后将剩余的N-k个数据依次与堆顶数据进行比较,如果比堆顶数据大,则将堆顶数据覆盖后向下调整时间复杂度(N-k)*log(N)总共的时间复杂度为O(......
  • 111. 二叉树的最小深度c
    /***Definitionforabinarytreenode.*structTreeNode{*intval;*structTreeNode*left;*structTreeNode*right;*};*/intmin(inti,intj){if(i>j)returnj;returni;}intminDepth(structTreeNode*root){......
  • 洛谷题单指南-二叉树-P4715 【深基16.例1】淘汰赛
    原题链接:https://www.luogu.com.cn/problem/P4715题意解读:计算亚军得主,注意能力值最高的肯定是冠军,但能力值第二高的不一定是亚军,因为有可能中途就遭遇冠军。解题思路:根据题意,两两比赛,一轮后再按顺序两两比赛,形如一棵二叉树,但解题其实用不到二叉树的数据结构可以看出,最后参与......
  • 【算法】【线性表】【数组】从中序与后序遍历序列构造二叉树
    1 题目给定两个整数数组 inorder 和 postorder ,其中 inorder 是二叉树的中序遍历, postorder 是同一棵树的后序遍历,请你构造并返回这颗 二叉树 。示例1:输入:inorder=[9,3,15,20,7],postorder=[9,15,7,20,3]输出:[3,9,20,null,null,15,7]示例2:输入:inor......