Leetcode 101:对称二叉树
题目描述
给定一个二叉树,检查它是否是镜像对称的。
解题思路
既然它是镜像的话,那么就是左右对称,这个我们可以使用一个递归来解决。我们令A等于这个树,B也等于这个树,假设A树和B树都只有一个结点(空结点也看做是一个结点)其实也就是两个树中至少一个树为NULL的时候,结果只会存在三种情况:
1.A的该结点为NULL,B的该结点也为NULL,即都是空结点,那么这两个树相等,自然是镜像,返回true;
2.A的该结点为NULL,B的该结点不为NULL(或者A的该结点不是NULL,B的该结点为NULL),那么不是镜像,返回false;
3.A和B均有值,但不相等,自然不是镜像,返回false。
我们把这个结点看做是其父结点的一个子树,然后逐层向上去扩展。
判断的时候是由上向下,只要两个结点值相等就继续递归。
代码实现
bool isSym(TreeNode* root1, TreeNode* root2){ if (root1 == nullptr && root2 == nullptr) return true; if (root1 == nullptr || root2 == nullptr) return false; if (root1->val != root2->val) return false; return isSym(root1->left, root2->right) && isSym(root1->right, root2->left);}bool isSymmetric(TreeNode* root) { return isSym(root, root);}
时间复杂度&空间复杂度
Leetcode 102:二叉树的层序遍历
题目描述
给定一个二叉树,返回其按层次遍历的节点值。 (即逐层地,从左到右访问所有节点)。
解题思路
这其实就是二叉树的BFS,但是和之前又有一点不同,那就是保存的结果不是一个vector,而是一个vector类型的vector数组,数组里面有多个vector,每个vector里面的元素是这一层的值。所以关键在于如何存储呢?那这个就可以借鉴之前做过的二叉树的右视角这个题,我们储存一个size,代表这一层有多少个元素,然后执行一个for循环,在这个for循环里面把元素push到一个tmp数组中,for循环完成后,把tmp
push到result即可。
但是不知道为什么,那个for循环如果我用while循环的话,就会超时,需要研究一下。
代码实现
vector<vector<int>> levelOrder(TreeNode* root) { vector<vector<int>> result; if (root == nullptr) return result; queue<TreeNode*>q; TreeNode* tt; q.push(root); while (!q.empty()) { int size = q.size(); vector<int>tmp; for(int i=0;i<size;i++) { tt = q.front(); tmp.push_back(tt->val); q.pop(); if (tt->left) q.push(tt->left); if (tt->right) q.push(tt->right); } result.push_back(tmp); } return result;}
执行用时和内存消耗
Leetcode 104:二叉树的最大深度
题目描述
给定一个二叉树,找出其最大深度。二叉树的深度为根节点到最远叶子节点的最长路径上的节点数。说明: 叶子节点是指没有子节点的节点。
示例
给定二叉树 [3,9,20,null,null,15,7],返回它的最大深度为3。
题目解析:递归法
如果一棵树只有一个结点,那么深度为1.如果根节点只有左子树而没有右子树,那么深度就是左子树深度+1;同理,对于右子树也是如此。如果既有左子树,也有右子树,那么该树的深度就是左右子树深度的最大值+1。所以可以利用递归的方式实现该题目。
代码实现:递归法
int maxDepth(TreeNode* root) { int Heightl,Heightr,MaxH; if(root) { Heightl=maxDepth(root->left); Heightr=maxDepth(root->right); MaxH=(Heightl>Heightr)?Heightl:Heightr; return MaxH+1; } else { return 0; } }
题目解析:广度优先
借鉴层序遍历的方法,只不过使用了deque,不具体说思路了,比较简单。
代码实现:广度优先
int maxDepth(TreeNode* root) { if(root==nullptr) return 0; deque<TreeNode* > q; q.push_back(root); int deep=0; while(!q.empty()) { ++deep; int len=q.size(); for(int i=1;i<=len;i++) { TreeNode *tt=q.front(); q.pop_front(); if(tt->left) q.push_back(tt->left); if(tt->right) q.push_back(tt->right); } } return deep; }
时间复杂度&空间复杂度
递归法:
广度优先:
可以看出,广度优先算法提升了速度,减小了内存消耗。