144. 二叉树的前序遍历

如果先执行移动根节点指向右子树，再执行pop执行会慢4ms

题目链接：https://leetcode-cn.com/problems/binary-tree-preorder-traversal/

执行用时：0 ms, 在所有 C++ 提交中击败了100.00% 的用户
内存消耗：8.2 MB, 在所有 C++ 提交中击败了54.13% 的用户

迭代

/**
 * 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) {}
 * };
 */
class Solution {
public:
    vector<int> preorderTraversal(TreeNode *root) {
        vector<int> res;
        if (root == nullptr) {
            return res;
        }
        stack<TreeNode*> S;
        while (root || !S.empty()){
            while (root){
                S.push(root);
                res.push_back(root->val);
                root = root->left;
            }
            root = S.top();
            S.pop();
            root = root ->right;
        }
        return res;
    }
};

class Solution {
    func preorderTraversal(_ root: TreeNode?) -> [Int] {
        guard let root = root else { return [] }
        
        var res: [Int] = []
        var stack: [TreeNode] = [root]
        while let node = stack.popLast() {
            res.append(node.val)
            //先存储右子树再存储左子树，出栈时即访问左子树
            if let right = node.right { stack.append(right) }
            if let left = node.left { stack.append(left) }
        }
        
        return res
    }
}

递归

执行用时：0 ms, 在所有 C++ 提交中击败了100.00% 的用户
内存消耗：8.1 MB, 在所有 C++ 提交中击败了70.94% 的用户

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;
        if (root == nullptr) {
            return res;
        }
        preorder(root,res);
        return res;
    }
};

swift 版

class Solution {
    var res: [Int] = []
    func preorderTraversal(_ root: TreeNode?) -> [Int] {
        if root == nil {
            return []
        }else{
            res.append(root?.val ?? -101)
            preorderTraversal(root?.left)
            preorderTraversal(root?.right)
        }
        return res
    }
}

执行用时：0 ms, 在所有 Java 提交中击败了100.00% 的用户
内存消耗：36.8 MB, 在所有 Java 提交中击败了36.11% 的用户

class Solution {
    public void preorder(Main.TreeNode root, List<Integer> res){
        if (root == null){
            return;
        }
        res.add(root.val );
        preorder(root.left,res);
        preorder(root.right,res);
    }
    public List<Integer> preorderTraversal(Main.TreeNode root) {
        List<Integer> res = new ArrayList<Integer>();
        preorder(root,res);
        return res;
    }
}