湖北外贸网站设计制作,跨境电商怎么发货到国外,谷建网站建设模板,好看的logo图案算法学习——LeetCode力扣二叉树篇1 144. 二叉树的前序遍历
144. 二叉树的前序遍历 - 力扣#xff08;LeetCode#xff09;
描述
给你二叉树的根节点 root #xff0c;返回它节点值的 前序 遍历。
示例
示例 1#xff1a;
输入#xff1a;root [1,null,2,3] 输出LeetCode
描述
给你二叉树的根节点 root 返回它节点值的 前序 遍历。
示例
示例 1
输入root [1,null,2,3] 输出[1,2,3]
示例 2
输入root [] 输出[]
示例 3
输入root [1] 输出[1]
示例 4
输入root [1,2] 输出[1,2]
示例 5
输入root [1,null,2] 输出[1,2]
提示
树中节点数目在范围 [0, 100] 内-100 Node.val 100
进阶
递归算法很简单你可以通过迭代算法完成吗
代码解析
递归遍历
前后中遍历的前后中指的是中间节点。
前序遍历 中左右 后续遍历 左右中 中序遍历 左中右
/*** 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:void Traversal(TreeNode* cur , vectorint result){if (cur nullptr) return;result.push_back(cur-val);Traversal(cur-left , result);Traversal(cur-right , result);}vectorint preorderTraversal(TreeNode* root) {vectorint result;Traversal(root,result);return result;}
};
非递归遍历
/*** 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:vectorint preorderTraversal(TreeNode* root) {vectorint result;stackTreeNode* my_stack; if(root nullptr) return result;my_stack.push(root);//前序遍历是中左右先处理一个中就是rootwhile(my_stack.empty() ! 1){TreeNode* my_node my_stack.top();//提前中节点my_stack.pop();//中节点压入结果result.push_back(my_node-val);//之后将中节点的左右子节点放到栈里作为未来的中节点//压入栈的顺序和弹出栈是相反的先遍历左再是右所有先压入右再压入左if(my_node-right ! nullptr) my_stack.push(my_node-right);if(my_node-left ! nullptr) my_stack.push(my_node-left);}return result;}
};
145. 二叉树的后序遍历
145. 二叉树的后序遍历 - 力扣LeetCode
描述
给你一棵二叉树的根节点 root 返回其节点值的 后序遍历 。
示例
示例 1
输入root [1,null,2,3] 输出[3,2,1]
示例 2
输入root [] 输出[]
示例 3
输入root [1] 输出[1]
提示
树中节点的数目在范围 [0, 100] 内-100 Node.val 100
进阶
递归算法很简单你可以通过迭代算法完成吗
代码解析
递归遍历
/*** 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:void traversal(TreeNode* cur , vectorint result){if (cur nullptr) return;traversal(cur-left , result);traversal(cur-right , result);result.push_back(cur-val);}vectorint postorderTraversal(TreeNode* root) {vectorint result;traversal(root, result);return result;}
};
非递归遍历
/*** 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:vectorint postorderTraversal(TreeNode* root) {vectorint result;stackTreeNode* my_stack;if(root nullptr) return result;my_stack.push(root);while(my_stack.empty() ! 1){TreeNode* my_node my_stack.top();my_stack.pop();//和前序一样但是变成中右左result.push_back(my_node-val);if(my_node-left ! nullptr) my_stack.push(my_node-left);if(my_node-right ! nullptr) my_stack.push(my_node-right); }//反转变成左右中reverse (result.begin() , result.end());return result;}
};
94. 二叉树的中序遍历
94. 二叉树的中序遍历 - 力扣LeetCode
描述
给定一个二叉树的根节点 root 返回 它的 中序 遍历 。
示例
示例 1
输入root [1,null,2,3] 输出[1,3,2]
示例 2
输入root [] 输出[]
示例 3
输入root [1] 输出[1]
提示
树中节点数目在范围 [0, 100] 内-100 Node.val 100
进阶
递归算法很简单你可以通过迭代算法完成吗
代码解析
递归遍历
/*** 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:void traversal(TreeNode* cur , vectorint result){if(curnullptr) return;traversal( cur-left , result);result.push_back( cur-val);traversal( cur-right , result);}vectorint inorderTraversal(TreeNode* root) {vectorint result;traversal(root,result);return result;}
};
非递归遍历
/*** 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:vectorint inorderTraversal(TreeNode* root) {vectorint result;stackTreeNode* my_stack;if(root nullptr) return result;TreeNode* cur root;while(cur ! nullptr || my_stack.empty() ! 1){if(cur ! nullptr)//找到cur的最左叶子节点{my_stack.push(cur);//找的过程中所有的左节点都存起来cur cur-left;}else//处理中节点和右节点{cur my_stack.top();//输出栈里之前存的左节点 这时左节点看作成中间节点my_stack.pop();result.push_back(cur-val);cur cur-right;//然后找刚才输出左节点作为中间点时的右节点}} return result;}
};
102. 二叉树的层序遍历
102. 二叉树的层序遍历 - 力扣LeetCode
描述
给你二叉树的根节点 root 返回其节点值的 层序遍历 。 即逐层地从左到右访问所有节点。
示例
示例 1
输入root [3,9,20,null,null,15,7] 输出[[3],[9,20],[15,7]] 示例 2
输入root [1] 输出[[1]] 示例 3
输入root [] 输出[]
提示
树中节点数目在范围 [0, 2000] 内-1000 Node.val 1000
代码解析
/*** 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 levelOrder(TreeNode* root) {vectorvectorint result;TreeNode* node ; //迭代节点queueTreeNode* my_que; //队列if(root nullptr) return result;else // 根节点进队列{my_que.push(root);}while(my_que.empty() ! 1){int size my_que.size(); //size是不断变化的指每一层级的点数量vectorint nums;//每一层级存放的点 //将每一层的点从队列弹出放入nums并且下一个层级点放入队列for(int i0 ; isize ; i) {node my_que.front(); //该层级的点弹出放入数组my_que.pop();nums.push_back(node-val);//每一个弹出点的下一个层级左右节点压入队列if(node-left ! nullptr) my_que.push(node-left);if(node-right ! nullptr) my_que.push(node-right);}result.push_back(nums);}return result;}
};
