赞
踩
二叉树的前序遍历就是,根 -> 左 -> 右,这样的次序。
解法1:递归,这个模板是前中后通用的
- class Solution {
- public:
- void preorder(TreeNode *root, vector<int> &res)
- {
- if (root != nullptr)
- {
- res.push_back(root->val);
- if (root->left != nullptr)
- preorder(root->left, res);
- if (root->right != nullptr)
- preorder(root->right, res);
- }
-
- }
-
- vector<int> preorderTraversal(TreeNode* root) {
- vector<int> res;
- preorder(root, res);
- return res;
- }
- };
解法2:迭代(手动建栈模拟系统操作)
- class Solution {
- public:
- vector<int> preorderTraversal(TreeNode* root) {
- vector<int> res;
- stack<TreeNode*> stk;
-
- while (root != nullptr || !stk.empty())
- {
- while (root != nullptr)
- {
- res.push_back(root->val);
- stk.push(root);
- root = root->left;
- }
- // 保证从栈里面出来的都是只有右孩子没探索过的
- root = stk.top();
- stk.pop();
- root = root->right;
- }
-
- return res;
- }
- };
解法3:Morris遍历
思想还是向左遍历之前,让当前节点左子树的最右节点指向自己,这样回溯的时候就能找到。
- class Solution {
- public:
- vector<int> preorderTraversal(TreeNode *root) {
- vector<int> res;
- TreeNode *p1 = root, *p2 = nullptr;
- // p2的设定是p1的左孩子
-
- // p1非空就继续循环
- while (p1 != nullptr) {
- p2 = p1->left;
- // 若p1有左孩子
- if (p2 != nullptr) {
- // p2是p1左子树的最右节点
- while (p2->right != nullptr && p2->right != p1) {
- p2 = p2->right;
- }
- // p2->right == nullptr 确定了该节点是第一次访问
- // 先把p1加入结果,再把p1左子树的最右节点指向p1,p1继续往左走
- if (p2->right == nullptr) {
- res.push_back(p1->val);
- p2->right = p1;
- p1 = p1->left;
- continue;
- // // p2->right == p1 说明该节点已经访问过,此时再访问到就置为空
- } else {
- p2->right = nullptr;
- }
- } // 若p1无左孩子,则把p1加入结果
- else {
- res.push_back(p1->val);
- }
- //
- // 1、其左孩子已经访问完毕,因此把p1的右孩子赋给p1
- // 要么就是在回溯的路上,要么就是到了一个全新的未被访问过的节点
- p1 = p1->right;
- }
- return res;
- }
- };
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。