二叉树的前中后序遍历
目录
题目
前序遍历:https://leetcode-cn.com/problems/binary-tree-preorder-traversal/
中序遍历:https://leetcode-cn.com/problems/binary-tree-inorder-traversal/
后序遍历:https://leetcode-cn.com/problems/binary-tree-postorder-traversal/
树的定义:
/**
* 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) {}
* };
*/
题解
前序遍历
前序遍历的顺序是:根 -> 左 -> 右。(这个顺序一开始还被我记错了qwq)
用递归的方式很简单:
class Solution {
public:
void preorder(TreeNode *root, vector<int> &res){
if (root == nullptr){
return;
}
res.push_back(root->val);
preorder(root->left, res);
preorder(root->right, res);
}
vector<int> preorderTraversal(TreeNode* root) {
vector<int> res;
preorder(root, res);
return res;
}
};
递归的本质是使用了栈。如果不想用递归,也可以显式地使用栈来做。但是看懂了递归后再看这种方法会觉得脑子疼。
中序遍历
改一下输出顺序就可以啦。
inorder(node->left, res);
res.push_back(node->val);
inorder(node->right, res);
后序遍历
postorder(node->left, res);
postorder(node->right, res);
res.push_back(node->val);
话说今天是思美节诶,图书馆的女生打扮的都好漂亮呀~祝节日快乐!