解题思路：

递归

按照前序遍历的定义来遍历

中 -> 左 -> 右

将值存储进数组就行了

迭代

因为要实现

中 -> 左 -> 右

右是最后遍历的，所以是先进后出(FILO)栈，先将根节点存进栈，然后每次取出栈顶，然后将右节点和左节点先后压入栈中

代码

Python

递归

1
2
3
4
5
6
7
8
9
10
11
class Solution:
    def preorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
        def dfs(node, lis) -> None:
            if node == None:
                return
            lis.append(node.val)
            dfs(node.left, lis)
            dfs(node.right, lis)
        result = []
        dfs(root, result)
        return result

迭代

1
2
3
4
5
6
7
8
9
10
11
12
class Solution:
    def preorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
        result = []
        stack = []
        stack.append(root)
        if root == None: return result
        while stack:
            node = stack.pop()
            result.append(node.val)
            stack.append(node.right) if node.right else ...
            stack.append(node.left) if node.left else ...
        return result

C++

递归

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
public:
    vector<int> preorderTraversal(TreeNode* root) {
        vector<int> tree_val;
        dfs(root, tree_val);
        return tree_val;
        
    }
    void dfs(TreeNode* node, vector<int> &tree_val) {
        if (node == NULL) return;
        tree_val.push_back(node->val);
        dfs(node->left, tree_val);
        dfs(node->right, tree_val);
    }
};

迭代

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public:
    vector<int> preorderTraversal(TreeNode* root) {
        stack<TreeNode*> st;
        vector<int>tree_val;
        if (root == NULL) return tree_val;
        st.push(root);
        while (!st.empty()) {
            TreeNode* node = st.top();
            st.pop();
            tree_val.push_back(node->val);
            if (node->right) st.push(node->right);
            if (node->left) st.push(node->left);
        }
        return tree_val;
    }
};