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; } };
