商标查询系统官网,优化二十条,大连网站建设短期培训班,企业网站注册域名的步骤102. 二叉树的层序遍历
层序遍历#xff0c;就是一层一层地遍历二叉树#xff0c;最常见的就是从上到下#xff0c;从左到右来遍历#xff0c;遍历的方法依然有两种#xff0c;第一种是借助队列#xff0c;第二种则是递归#xff0c;都算是很简单、很容易理解的方法就是一层一层地遍历二叉树最常见的就是从上到下从左到右来遍历遍历的方法依然有两种第一种是借助队列第二种则是递归都算是很简单、很容易理解的方法下面来分别介绍一下。
队列法
使用队列法讲究的就是一个简单粗暴顺着做下去就行了。
首先要定义一个队列这个队列的元素都得是二叉树结点因为它是用来暂存二叉树的一层的。先是把根结点入队当然如果连根结点都没有的话就直接返回空数组了要返回的是保存各层元素的二维数组用vector容器实现
接着就用vector定义一个保存遍历下来的元素的二维数组作为result来最终返回答案
现在就开始遍历了我们用的是while循环当队列为空时停止在一轮循环中队列存的是这层要遍历的结点所以先定义一个size来保存未经遍历的层结点数因为下面我们在遍历一个结点后就要把它出队以便于存入下一层的结点
遍历中使用一个一维数组保存元素值然后就把这个结点的左右子结点依次入队因为是队列就不用像栈那样反着来。每层遍历结束后就把遍历得到的元素数组push进result二维数组里。
具体代码如下
class Solution {
public:vectorvectorint levelOrder(TreeNode* root) {queueTreeNode* que;vectorvectorint result;if (root ! NULL) que.push(root);while (!que.empty()) {int size que.size();vectorint vec;for (int i 0; i size; i) {TreeNode* node que.front();que.pop();vec.push_back(node-val);if (node-left) que.push(node-left);if (node-right) que.push(node-right);}result.push_back(vec);}return result;}
};
递归法
这个不用掌握了解一下即可。但是下面的两道还是优先使用递归来做。
class Solution {
public:void order(TreeNode* cur, vectorvectorint result, int depth) {if (cur nullptr) return;if (result.size() depth) result.push_back(vectorint());result[depth].push_back(cur-val);order(cur-left, result,depth 1);order(cur-right, result, depth 1);}vectorvectorint levelOrder(TreeNode* root) {vectorvectorint result;int depth 0;order(root, result, depth);return result;}
};
226. 翻转二叉树
题目 思路
看到翻转你可能会先想到一层一层地将结点翻转但其实不用这么复杂稍微观察一下就知道只需要翻转每个结点的两个子结点即可所以这里就可以用递归遍历的方法来做先对调两个子结点再遍历子结点最后返回根结点即可。
盲区
随想录刷到这里才知道swap函数还可以用来对调两个二叉树结点长知识了
swap(root-left, root-right);
代码
class Solution {
public:TreeNode* invertTree(TreeNode* root) {if (root NULL) return root;swap(root-left, root-right);invertTree(root-left);invertTree(root-right);return root;}
};
101. 对称二叉树
题目 思路
还是用递归来做每次递归判断对称的两个结点若其中一个为空则返回false两个都为空则返回true接着都是不为空的此时就判断两个结点值是否相等不相等就返回false否则就接着往下递归先递归判断左边的左孩子和右边的右孩子再递归判断左边的右孩子和右边的左孩子这样就是对称位置的结点来判断是否相等了将判断结果分别赋值给一个布尔变量两个布尔变量都为true时就返回true。
代码
class Solution {
public:bool compare(TreeNode* left, TreeNode* right) {if (left NULL right ! NULL) return false;else if (left ! NULL right NULL) return false;else if (left NULL right NULL) return true;else if (left-val ! right-val) return false;bool outside compare(left-left, right-right);bool inside compare(left-right, right-left);bool isSame outside inside;return isSame;}bool isSymmetric(TreeNode* root) {if (root NULL) return true;return compare(root-left, root-right);}
};
