LeetCode[144] 二叉树的前序遍历（迭代）-蒲公英云

LeetCode[144] 二叉树的前序遍历（迭代）

前言：今天的 LeetCode 上的每日一题，二叉树的前序遍历，用 C++ 实现

题目描述

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

算法分析

二叉树的递归前序遍历，先访问根节点，再访问左子树，最后访问右子树
迭代算法，利用栈保存节点信息，完成遍历操作

代码实现

递归代码：

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

迭代代码：注意入栈顺序，左子树先出栈，因此右子树先入栈

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