二叉树刷题Leetcode

文章目录 104.二叉树的最大深度100.相同的树965.单值二叉树

104.二叉树的最大深度

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

处理二叉树最大深度的问题时，二叉树可以分为左子树，右子树，根。二叉树最大深度=（1+max{左子树最大深度，右子树最大深度}),1代表根。这样二叉树的最大深度就可以无限的递推下去，直到左子树，右子树都为空。所以边界问题就是当节点为空是返回0 if(root==NULL) return 0;。处理递归时，核心是思考整棵树与其左右子树的关系，而不是不停地想子问题的过程。子问题和原问题是相似的，他们执行的代码也是相同的，只要代码的边界条件和非边界条件的逻辑写对了就行了。

100.相同的树

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

比较两棵树是否相同时，首先，根节点必须是相同的，然后就是看2棵左子树是否相同，2棵右子树是否相同。所以要解决的子问题就是左边2棵子树是否相同，右边2棵子树是否相同。那么边界条件是什么呢？如果2棵树有一个是空的，那么就无法递归了，此时我们可以判断一下，如果2个节点都是空就返回true，否则返回false.

965.单值二叉树

bool isUnivalTree(struct TreeNode* root) { if(root==NULL) return true; if(root->left!=NULL) { if(root->val!=root->left->val||!isUnivalTree(root->left)) return false; } if(root->right!=NULL) { if(root->val!=root->right->val||!isUnivalTree(root->right)) return false; } return true; }

这题我们像前面2题的思路看一看，边界条件和子问题分别是什么呢。子问题就是左子树右子树里的值都要等于根节点的值，边界条件就是递归到节点为空时返回true，前面递归过程中如果左子树或右子树的值和根的值不相等或在左子树或右子树中存在不等的值时返回false