js搜索网站开发,手机app是什么意思,wordpress新建文章页面,中山网站建设文化价格题目#xff1a;
给你二叉树的根节点 root #xff0c;返回其节点值的 层序遍历 。 #xff08;即逐层地#xff0c;从左到右访问所有节点#xff09;。 输入#xff1a;root [3,9,20,null,null,15,7] 输出#xff1a;[[3],[9,20],[15,7]] 解题思路#xff1a;迭代法…题目
给你二叉树的根节点 root 返回其节点值的 层序遍历 。 即逐层地从左到右访问所有节点。 输入root [3,9,20,null,null,15,7] 输出[[3],[9,20],[15,7]] 解题思路迭代法实现
层序遍历一般都是用广度优先 遍历那么迭代法就是最直观的且最简单的。
借助一个队列层层遍历将每一层的节点入队出队时由于队列先进先出的特点也会按顺序出队。在出队前我们先计算队列的长度len这个长度len就相当于当前层一共有len个节点所以我们只需要将len个节点出队即可其他的节点都是下一层的我们先不去管所以在循环出队时结束条件就是len0。
源代码如下
//迭代法
class Solution {
public:vectorvectorint levelOrder(TreeNode* root) {queueTreeNode* qq;//定义一个栈vectorvectorint res;//结果数组if(rootnullptr) return res;//root为空直接返回空数组即可qq.push(root);//先将根节点入队while(!qq.empty())//循环结束条件使队列为空{vectorint temp;//定义一个临时数组用来存放出队的元素int lenqq.size();//计算当前队列的长度while(len)//长度len变为0时说明当前层的节点已经全部出队了{TreeNode* nodeqq.front();//队头元素qq.pop();//出队temp.push_back(node-val);//节点放入temp中//继续将节点的左右节点依次入队if(node-left!nullptr) qq.push(node-left);if(node-right!nullptr) qq.push(node-right);len--;//记得每出队一个元素就要len-1}res.push_back(temp);//临时数组放入res中}return res;}
};
解题思路递归法实现
递归也就是我们常说的深度优先遍历需要设置一个index用来记录遍历到哪一层了将节点放入到自己的层中。
源代码如下
//递归法
class Solution {
public:vectorvectorint res;//定义res结果数组void dfs(TreeNode* root,int index){if(!root) return ;//root为空直接return//如果index超过数组的大小那么就添加一个新的层//eg.原本res[3],[2,5] index2 res.size()2//那么现在res[3],[2,5],[]if(indexres.size()){res.push_back(vectorint());}//将节点的值放入到相应的层中res[index].push_back(root-val);//继续递归节点的左子树和右子树记得index要不断更新每次1dfs(root-left,index1);dfs(root-right,index1);}vectorvectorint levelOrder(TreeNode* root) {dfs(root,0);return res;}
}
