网站架构包含哪几个部分,phpcms和帝国cms哪个好,租注册地址一年多少费用,网站备案会过期吗103. 二叉树的锯齿形层序遍历
题目大意#xff1a;将原先的层次遍历改为蛇形遍历#xff0c;那么我们需要在102. 二叉树的层序遍历的基础上进行改进#xff0c;首先蛇形走位#xff08;先从左往右#xff0c;再从右往左进行下一层遍历#xff0c;以此类推#xff0c;层…103. 二叉树的锯齿形层序遍历
题目大意将原先的层次遍历改为蛇形遍历那么我们需要在102. 二叉树的层序遍历的基础上进行改进首先蛇形走位先从左往右再从右往左进行下一层遍历以此类推层与层之间交替进行 让我们想到设置 bool 值进行左右方向控制遍历方向使其进入队列但这样不如直接使用双端队列。
如果是奇数行正序进入队列偶数行逆序进入----》奇数行元素从队头插入偶数行从队尾插入。 /*** Definition for a binary tree node.* struct TreeNode {* int val;* TreeNode *left;* TreeNode *right;* TreeNode() : val(0), left(nullptr), right(nullptr) {}* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left),* right(right) {}* };*/
class Solution {
public:vectorvectorint ans;vectorvectorint zigzagLevelOrder(TreeNode* root) {if (!root)return ans;TreeNode* visitedroot;queueTreeNode* q;bool left 1; // 控制左右孩子进入顺序q.push(visited);while (!q.empty()) {dequeint levelList;int cursize q.size();// ans.push_back(vectorint());for (int i 0; i cursize; i) {q.pop();if (left)levelList.push_back(visited-val);elselevelList.push_front(visited-val);if (visited-left) q.push(visited-left);if (visited-right) q.push(visited-right);visited q.front();}left !left;ans.emplace_back(vectorint{levelList.begin(), levelList.end()});}return ans;}
};
下面来两道递归题目树这块递归题目很多 104. 二叉树的最大深度
1.确定递归函数的参数和返回值参数就是传入树的根节点返回就返回这棵树的深度所以返回值为int类型。
2.确定终止条件如果为空节点的话就返回0表示高度为0。
3.确定单层递归的逻辑先求它的左子树的深度再求右子树的深度最后取左右深度最大的数值 再1 加1是因为算上当前中间节点就是目前节点为根节点的树的深度。
class Solution {
public:int ans0;int maxDepth(TreeNode* root) {//dfsif(!root) return 0;ansmax(maxDepth(root-left),maxDepth(root-right));return ans1;}
};
236. 二叉树的最近公共祖先 class Solution {
public:TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {if(proot||qroot||!root) return root;TreeNode *leftlowestCommonAncestor(root-left,p,q);TreeNode *rightlowestCommonAncestor(root-right,p,q);if(!left) return right;if(!right) return left;return root;}
};
