算法学习——LeetCode力扣二叉树篇1

算法学习——LeetCode力扣二叉树篇1

144. 二叉树的前序遍历

144. 二叉树的前序遍历 - 力扣（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 , vector<int> &result){if (cur == nullptr) return;result.push_back(cur->val);Traversal(cur->left , result);Traversal(cur->right , result);}vector<int> preorderTraversal(TreeNode* root) {vector<int> 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:vector<int> preorderTraversal(TreeNode* root) {vector<int> result;stack<TreeNode*> 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 , vector<int> &result){if (cur == nullptr) return;traversal(cur->left , result);traversal(cur->right , result);result.push_back(cur->val);}vector<int> postorderTraversal(TreeNode* root) {vector<int> 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:vector<int> postorderTraversal(TreeNode* root) {vector<int> result;stack<TreeNode*> 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 , vector<int> &result){if(cur==nullptr) return;traversal( cur->left , result);result.push_back( cur->val);traversal( cur->right , result);}vector<int> inorderTraversal(TreeNode* root) {vector<int> 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:vector<int> inorderTraversal(TreeNode* root) {vector<int> result;stack<TreeNode*> 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:vector<vector<int>> levelOrder(TreeNode* root) {vector<vector<int>> result;TreeNode* node ; //迭代节点queue<TreeNode*> my_que; //队列if(root == nullptr) return result;else // 根节点进队列{my_que.push(root);}while(my_que.empty() != 1){int size = my_que.size(); //size是不断变化的，指每一层级的点数量vector<int> nums;//每一层级存放的点  //将每一层的点从队列弹出放入nums，并且下一个层级点放入队列for(int i=0 ; i<size ; 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;}
};