leetcode 144 145 94二叉树的三种递归遍历
2023-09-27 14:29:24 时间
leetcode144 递归前序遍历
前后中遍历的前后中,指的是中间节点。
- 前序遍历 :中左右
- 后续遍历: 左右中
- 中序遍历: 左中右
/**
* 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;
}
};
leetcode145 递归后序遍历
/**
* 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;
}
};
leetcode94 递归中序遍历
/**
* 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> result;
void back_track(TreeNode* cur)
{
if(cur == nullptr) return;
result.push_back(cur->val);
back_track(cur->left);
back_track(cur->right);
}
vector<int> preorderTraversal(TreeNode* root) {
back_track(root);
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> result;
void back_track(TreeNode* cur)
{
if(cur == nullptr) return;
back_track(cur->left);
back_track(cur->right);
result.push_back(cur->val);
}
vector<int> postorderTraversal(TreeNode* root) {
back_track(root);
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> result;
void back_track(TreeNode* cur)
{
if(cur == nullptr) return;
back_track(cur->left);
result.push_back(cur->val);
back_track(cur->right);
}
vector<int> inorderTraversal(TreeNode* root) {
back_track(root);
return result;
}
};
相关文章
- (LeetCode)用两个栈实现一个队列
- 111、【树与二叉树】leetcode ——669. 修剪二叉搜索树:递归法(C++版本)
- 109、【树与二叉树】leetcode ——701. 二叉搜索树中的插入操作:递归法+双指针迭代法(C++版本)
- 103、【树与二叉树】leetcode ——700. 二叉搜索树中的搜索:递归法+迭代法(C++版本)
- 102、【树与二叉树】leetcode ——654. 最大二叉树(C++版本)
- 92、【树与二叉树】leetcode ——111. 二叉树的最小深度:层次遍历+先序DFS+后序DFS[子问题分解](C++版本)
- 【leetcode】103:二叉树的锯齿形层序遍历
- [LeetCode] Non-negative Integers without Consecutive Ones 非负整数不包括连续的1
- [LeetCode] 105. Construct Binary Tree from Preorder and Inorder Traversal 由先序和中序遍历建立二叉树
- [LeetCode] 145. Binary Tree Postorder Traversal 二叉树的后序遍历
- LeetCode合并二叉树
- leetcode 145. Binary Tree Postorder Traversal 二叉树的后序遍历 (中等)
- leetcode 106. Construct Binary Tree from Inorder and Postorder Traversal 从中序与后序遍历序列构造二叉树(中等)
- leetcode 101. Symmetric Tree 对称二叉树(简单)
- leetcode算法111.二叉树的最小深度
- leetcode算法94.二叉树的中序遍历