二叉树的遍历
分为三种：前序、后序和中序，其中最容易用栈改写的是后序。
前序(Preorder)：Root -> Left -> Right⌗
class Solution {
public:
void processPreorderTraversal(TreeNode* root, vector<int> & collector) {
if (root == nullptr) {
return;
}
processPreorderTraversal(root->left, collector);
collector.push_back(root->val);
processPreorderTraversal(root->right, collector);
}
vector<int> inorderTraversal(TreeNode* root) {
vector<int> ret;
if (root == nullptr) {
return ret;
}
processPreorderTraversal(root, ret);
return ret;
}
};
中序(Inorder): Left -> Root -> Right⌗
class Solution {
public:
void processInorderTraversal(TreeNode* root, vector<int> & collector) {
if (root == nullptr) {
return;
}
processInorderTraversal(root->left, collector);
collector.push_back(root->val);
processInorderTraversal(root->right, collector);
}
vector<int> inorderTraversal(TreeNode* root) {
vector<int> ret;
if (root == nullptr) {
return ret;
}
processInorderTraversal(root, ret);
return ret;
}
};
后序(Postorder)：Left -> Right -> Root⌗
class Solution {
public:
void processPostorderTraversal(TreeNode* root, vector<int> & collector) {
if (root == nullptr) {
return;
}
processPostorderTraversal(root->left, collector);
processPostorderTraversal(root->right, collector);
collector.push_back(root->val);
}
vector<int> postorderTraversal(TreeNode* root) {
vector<int> ret;
if (root == nullptr) {
return ret;
}
processPostorderTraversal(root, ret);
return ret;
}
};