跳转至

144.二叉树的前序遍历 (Medium)*

题目描述*

给定一个二叉树，返回它的 前序 遍历。

示例*

输入: [1,null,2,3] 

   1
    \
     2
    /
   3

输出: [1,2,3]

进阶*

递归算法很简单，你可以通过迭代算法完成吗？

代码*

最简单的就是递归。

用栈实现的迭代，每遇到一个结点 A，就立即访问它，因此每棵子树都访问其根结点，遍历完左子树后，再遍历右子树。因此，访问根节点后，需要将右子树入栈。

这两种都需要使用额外空间保存结点，Morris Traversal 算法，将当前结点左子树的最右结点的右指针指向当前结点，这样无需额外空间即可遍历。

class Solution {
public:
    void visitPre(TreeNode *root, vector<int>& res) {
        if(root != nullptr) {
            res.push_back(root->val);
            visitPre(root->left, res);
            visitPre(root->right, res);
        }
    }
    vector<int> preorderTraversal(TreeNode* root) {
        vector<int> res;
        visitPre(root, res);
        return res;
    }
};

class Solution {
public:
    vector<int> preorderTraversal(TreeNode* root) {
        vector<int> res;
        stack<TreeNode*> helpStack;
        TreeNode *cur = root;
        while(cur != nullptr || !helpStack.empty()) {
            while(cur != nullptr) {
                res.push_back(cur->val);
                helpStack.push(cur->right);
                cur = cur->left;
            }
            cur = helpStack.top();
            helpStack.pop();
        }
        return res;
    }
};

class Solution {
public:
    vector<int> preorderTraversal(TreeNode* root) {
        vector<int> res;
        TreeNode *cur = root;
        while(cur != nullptr) {
            if(cur->left == nullptr) {
                res.push_back(cur->val);
                cur = cur->right;
            }else {
                // 找左子树的最右点，即前序遍历下 cur 结点的前驱
                TreeNode *l = cur->left;
                while(l->right != nullptr && l->right != cur) {
                    l = l->right;
                }
                if(l->right == nullptr) {
                    res.push_back(cur->val);
                    l->right = cur;
                    cur = cur->left;
                }else if(l->right == cur) {
                    l->right = nullptr;
                    cur = cur->right;
                }
            }
        }
        return res;
    }
};
最后更新: July 23, 2022