打开APP
userphoto
未登录

开通VIP,畅享免费电子书等14项超值服

开通VIP
LeetCode——树

目录

递归

104. 二叉树的最大深度

题目描述:给定一个二叉树,找出其最大深度。

int maxDepth(struct TreeNode* root){    if(root==NULL) return 0;    int maxLeft=maxDepth(root->left) 1;    int maxRight=maxDepth(root->right) 1;    return maxLeft>maxRight?maxLeft:maxRight;}

110. 平衡二叉树

题目描述:给定一个二叉树,判断它是否是高度平衡的二叉树。

bool isBalanced(struct TreeNode* root){    return maxDepth(root)!=-1;}int maxDepth(struct TreeNode *root){    if(root==NULL) return 0;    int maxLeft=maxDepth(root->left);    if(maxLeft==-1) return -1;    int maxRight=maxDepth(root->right);    if(maxRight==-1) return -1;    int x=abs(maxRight-maxLeft);    if(x>1) return -1;    return (maxLeft>maxRight?maxLeft:maxRight) 1;}

543. 二叉树的直径

题目描述:给定一棵二叉树,你需要计算它的直径长度。一棵二叉树的直径长度是任意两个结点路径长度中的最大值。这条路径可能穿过也可能不穿过根结点。

分析:直径为左子树最大高度 右子树最大高度,在递归过程中实时更新最大的直径即可

int diameterOfBinaryTree(struct TreeNode* root){    int maxLen=0;    maxDepth(root,&maxLen);    return maxLen;}int maxDepth(struct TreeNode* root,int *maxLen){    if(root==NULL) return 0;    int maxLeft=maxDepth(root->left,maxLen);    int maxRight=maxDepth(root->right,maxLen);    int tmpLen=maxLeft maxRight;    if(tmpLen>*maxLen) *maxLen=tmpLen;    return (maxLeft>maxRight?maxLeft:maxRight) 1;}

226. 翻转二叉树

题目描述:翻转一棵二叉树。

分析:后序遍历求解

struct TreeNode* invertTree(struct TreeNode* root){    if(root==NULL) return NULL;    struct TreeNode *l=invertTree(root->left);    struct TreeNode *r=invertTree(root->right);    root->left=r;    root->right=l;    return root;}

617. 合并二叉树

题目描述:给定两个二叉树,想象当你将它们中的一个覆盖到另一个上时,两个二叉树的一些节点便会重叠。

你需要将他们合并为一个新的二叉树。合并的规则是如果两个节点重叠,那么将他们的值相加作为节点合并后的新值,否则不为 NULL 的节点将直接作为新二叉树的节点。

分析:

利用前序遍历,用两个指针分别指向两棵树对应位置

递归终止条件:指针到达某一棵树的叶子结点,于是返回另一个结点指针

返回给上一层的信息:返回一棵处理好的根节点

本轮的任务:从宏观来看,本轮要连接下一层返回的两个根节点,组成一棵树,并将当前位置的结点数值相加

struct TreeNode* mergeTrees(struct TreeNode* t1, struct TreeNode* t2){    if(t1==NULL) return t2;    if(t2==NULL) return t1;    t1->val =t2->val;    t1->left=mergeTrees(t1->left,t2->left);    t1->right=mergeTrees(t1->right,t2->right);    return t1;}

112. 路径总和

题目描述:给定一个二叉树和一个目标和,判断该树中是否存在根节点到叶子节点的路径,这条路径上所有节点值相加等于目标和。

bool hasPathSum(struct TreeNode* root, int sum){    if(root==NULL){        return false;    }    if(root->left==NULL&&root->right==NULL&&root->val==sum){//叶子结点,且其值为sum        return true;    }    return hasPathSum(root->left,sum-root->val)||hasPathSum(root->right,sum-root->val);//左右结点都没有路径才返回false}

437. 路径总和 III

题目描述:给定一个二叉树,它的每个结点都存放着一个整数值。找出路径和等于给定数值的路径总数。路径不需要从根节点开始,也不需要在叶子节点结束,但是路径方向必须是向下的(只能从父节点到子节点)。

分析:

从宏观上看,对于树中的一个结点,总的路径数包含两部分:

  1. 经过该结点的路径数
  2. 不经过该该结点,即在其子树上的路径
int pathSumWithRoot(struct TreeNode* root,int sum){    if(root==NULL) return 0;    int ret=0;    if(sum==root->val) ret  ;    ret =pathSumWithRoot(root->left,sum-root->val) pathSumWithRoot(root->right,sum-root->val);    return ret;}int pathSum(struct TreeNode* root, int sum){    if(root==NULL) return 0;    return pathSum(root->left,sum) pathSum(root->right,sum) pathSumWithRoot(root,sum);}

572. 另一个树的子树

题目描述:给定两个非空二叉树 s 和 t,检验 s 中是否包含和 t 具有相同结构和节点值的子树。s 的一个子树包括 s 的一个节点和这个节点的所有子孙。s 也可以看做它自身的一棵子树。

分析:

双递归求解,外层递归用于遍历s树的每个结点,内层递归用于判断以当前结点为根节点的子树是否与t树相同

内层递归终止条件:两个指针都为NULL,说明这条路径上对应结点值是相同的,返回true,其余情况都为false

bool isSameTree(struct TreeNode *s,struct TreeNode *t){    if(s==NULL&&t==NULL) return true;    if(s==NULL||t==NULL) return false;    if(s->val!=t->val) return false;    return isSameTree(s->left,t->left)&&isSameTree(s->right,t->right);}bool isSubtree(struct TreeNode* s, struct TreeNode* t){    if(s==NULL) return false;    return isSameTree(s,t)||isSubtree(s->left,t)||isSubtree(s->right,t);}

101. 对称二叉树

题目描述:给定一个二叉树,检查它是否是镜像对称的。

分析:

首先,如果给定是空树,则必然对称

其次分析,如果有子树,则左子树的左结点等于右子树的右结点,左子树右结点等于右子树左结点

bool child(struct TreeNode* l,struct TreeNode* r){    if(l==NULL&&r==NULL) return true;    if(l==NULL||r==NULL) return false;    if(l->val!=r->val) return false;    return child(l->left,r->right)&&child(l->right,r->left);}bool isSymmetric(struct TreeNode* root){    if(root==NULL) return true;    return child(root->left,root->right);}
来源:https://www.icode9.com/content-4-677501.html
本站仅提供存储服务,所有内容均由用户发布,如发现有害或侵权内容,请点击举报
打开APP,阅读全文并永久保存 查看更多类似文章
猜你喜欢
类似文章
【热】打开小程序,算一算2024你的财运
二叉树两个结点的最低共同父结点
每日一题 剑指offer(二叉树中和为某一值的路径)
剑指offer 58对称的二叉树
求二叉树的结点个数
B+ 树算法与源码(C语言描述)
剑指offer(C++)-JZ82:二叉树中和为某一值的路径(一)(数据结构-树)
更多类似文章 >>
生活服务
热点新闻
分享 收藏 导长图 关注 下载文章
绑定账号成功
后续可登录账号畅享VIP特权!
如果VIP功能使用有故障,
可点击这里联系客服!

联系客服