wordpress无法更换头像,汕头网站推广seo,wordpress图片像素,网络服务提供者接到权利人目录
一、二叉树层序遍历
非递归法
递归法
相关题目#xff08;10题#xff09; 二、#xff08;leetcode 226#xff09;翻转二叉树
递归法
层序遍历
深度优先遍历
1#xff09;非统一写法——前序遍历
2#xff09; 统一写法——前序遍历
三、#xff08;le…目录
一、二叉树层序遍历
非递归法
递归法
相关题目10题 二、leetcode 226翻转二叉树
递归法
层序遍历
深度优先遍历
1非统一写法——前序遍历
2 统一写法——前序遍历
三、leetcode 101对称二叉树
递归法
迭代法
1使用队列
2使用栈 一、二叉树层序遍历
借用队列实现因为队列先进先出符合层序遍历逻辑
非递归法 class Solution {
public:vectorvectorint levelOrder(TreeNode* root) {queueTreeNode* que;if (root ! NULL) que.push(root);vectorvectorint result;while (!que.empty()) {int size que.size();vectorint vec;// 这里一定要使用固定大小size不要使用que.size()因为que.size是不断变化的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;}
};
相关题目10题
102.二叉树的层序遍历(opens new window)107.二叉树的层次遍历II(opens new window)199.二叉树的右视图(opens new window)637.二叉树的层平均值(opens new window)429.N叉树的层序遍历(opens new window)515.在每个树行中找最大值(opens new window)116.填充每个节点的下一个右侧节点指针(opens new window)117.填充每个节点的下一个右侧节点指针II(opens new window)104.二叉树的最大深度(opens new window)111.二叉树的最小深度 二、leetcode 226翻转二叉树
力扣题目链接 状态递归法、层序遍历AC深度优先遍历还需回顾原始代码就没有看的很清楚 递归法
前序、后序遍历都可以中序不行
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;}
}; 中序遍历不行的原因 传统的递归不行注意最后还是遍历左孩子因为中间节点翻转时已经将左右调转了 class Solution {
public:TreeNode* invertTree(TreeNode* root) {if (root NULL) return root;invertTree(root-left); // 左swap(root-left, root-right); // 中invertTree(root-left); // 注意 这里依然要遍历左孩子因为中间节点已经翻转了return root;}
}; 层序遍历
class Solution {
public:TreeNode* invertTree(TreeNode* root) {queueTreeNode* que;if (root ! NULL) que.push(root);while (!que.empty()) {int size que.size();for (int i 0; i size; i) {TreeNode* node que.front();que.pop();swap(node-left, node-right); // 节点处理if (node-left) que.push(node-left);if (node-right) que.push(node-right);}}return root;}
};
深度优先遍历
1非统一写法——前序遍历
class Solution {
public:TreeNode* invertTree(TreeNode* root) {if (root NULL) return root;stackTreeNode* st;st.push(root);while(!st.empty()) {TreeNode* node st.top(); // 中st.pop();swap(node-left, node-right);if(node-right) st.push(node-right); // 右if(node-left) st.push(node-left); // 左}return root;}
};
2 统一写法——前序遍历
class Solution {
public:TreeNode* invertTree(TreeNode* root) {stackTreeNode* st;if (root ! NULL) st.push(root);while (!st.empty()) {TreeNode* node st.top();if (node ! NULL) {st.pop();if (node-right) st.push(node-right); // 右if (node-left) st.push(node-left); // 左st.push(node); // 中st.push(NULL);} else {st.pop();node st.top();st.pop();swap(node-left, node-right); // 节点处理逻辑}}return root;}
};
三、leetcode 101对称二叉树
力扣题目链接 状态递归法顺利AC迭代法中使用栈的思路清楚并AC使用队列的部分有点乱 递归法
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;else return compare(left-left, right-right) compare(left-right, right-left);}bool isSymmetric(TreeNode* root) {if (root NULL) return true;return compare(root-left, root-right);}
};
迭代法
1使用队列 class Solution {
public:bool isSymmetric(TreeNode* root) {if (root NULL) return true;queueTreeNode* que;que.push(root-left); // 将左子树头结点加入队列que.push(root-right); // 将右子树头结点加入队列while (!que.empty()) { // 接下来就要判断这两个树是否相互翻转TreeNode* leftNode que.front(); que.pop();TreeNode* rightNode que.front(); que.pop();if (!leftNode !rightNode) { // 左节点为空、右节点为空此时说明是对称的continue;}// 左右一个节点不为空或者都不为空但数值不相同返回falseif ((!leftNode || !rightNode || (leftNode-val ! rightNode-val))) {return false;}que.push(leftNode-left); // 加入左节点左孩子que.push(rightNode-right); // 加入右节点右孩子que.push(leftNode-right); // 加入左节点右孩子que.push(rightNode-left); // 加入右节点左孩子}return true;}
};
2使用栈
把左右两个子树要比较的元素顺序放进一个容器然后成对成对的取出来进行比较
class Solution {
public:bool isSymmetric(TreeNode* root) {if (root NULL) return true;stackTreeNode* st; // 这里改成了栈st.push(root-left);st.push(root-right);while (!st.empty()) {TreeNode* leftNode st.top(); st.pop();TreeNode* rightNode st.top(); st.pop();if (!leftNode !rightNode) {continue;}if ((!leftNode || !rightNode || (leftNode-val ! rightNode-val))) {return false;}st.push(leftNode-left);st.push(rightNode-right);st.push(leftNode-right);st.push(rightNode-left);}return true;}
};
