目录
题目描述:给定一个二叉树,找出其最大深度。
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;}
题目描述:给定一个二叉树,判断它是否是高度平衡的二叉树。
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;}
题目描述:给定一棵二叉树,你需要计算它的直径长度。一棵二叉树的直径长度是任意两个结点路径长度中的最大值。这条路径可能穿过也可能不穿过根结点。
分析:直径为左子树最大高度 右子树最大高度,在递归过程中实时更新最大的直径即可
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;}
题目描述:翻转一棵二叉树。
分析:后序遍历求解
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;}
题目描述:给定两个二叉树,想象当你将它们中的一个覆盖到另一个上时,两个二叉树的一些节点便会重叠。
你需要将他们合并为一个新的二叉树。合并的规则是如果两个节点重叠,那么将他们的值相加作为节点合并后的新值,否则不为 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;}
题目描述:给定一个二叉树和一个目标和,判断该树中是否存在根节点到叶子节点的路径,这条路径上所有节点值相加等于目标和。
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}
题目描述:给定一个二叉树,它的每个结点都存放着一个整数值。找出路径和等于给定数值的路径总数。路径不需要从根节点开始,也不需要在叶子节点结束,但是路径方向必须是向下的(只能从父节点到子节点)。
分析:
从宏观上看,对于树中的一个结点,总的路径数包含两部分:
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);}
题目描述:给定两个非空二叉树 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);}
题目描述:给定一个二叉树,检查它是否是镜像对称的。
分析:
首先,如果给定是空树,则必然对称
其次分析,如果有子树,则左子树的左结点等于右子树的右结点,左子树右结点等于右子树左结点
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
联系客服