面试经典算法题20-二叉树的前序遍历

LeetCode.144

问题描述

给你二叉树的根节点 root ，返回它节点值的前序遍历。

示例 1：

输入：root = [1,null,2,3]
输出：[1,2,3]

示例 2：

输入：root = []
输出：[]

示例 3：

输入：root = [1]
输出：[1]

示例 4：

输入：root = [1,2]
输出：[1,2]

示例 5：

输入：root = [1,null,2]
输出：[1,2]

提示：

树中节点数目在范围 [0, 100] 内
-100 <= Node.val <= 100

思路

递归

使用递归进行前序遍历，即根节点 -> 左子树 -> 右子树。
对于每个节点，先将节点的值加入结果数组，然后递归遍历左子树和右子树。

迭代

遍历，先将根节点压入栈中。然后循环执行以下操作：

弹出栈顶节点，如果节点为空，则继续弹出，直到遇到非空节点。
对于非空节点，先将其值加入结果数组，然后将右子节点压入栈中，再将左子节点压入栈中，保证左子节点在右子节点之前被访问。

图解

这里给大家图解一下迭代的方法。

先将根节点压入栈中。

当栈不为空时，弹出栈顶元素，遍历右子节点，再遍历左子节点。

依次弹出栈顶元素，并添加到结果集。

参考代码

C++

递归

cpp

#include <iostream>
#include <vector>
#include <stack>
#include <unordered_map>

using namespace std;

// 定义二叉树节点
struct TreeNode {
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};

class Solution {
public:
    vector<int> preorderTraversal(TreeNode* root) {
        vector<int> result;
        preorder(root, result);
        return result;
    }

    void preorder(TreeNode* root, vector<int>& result) {
        if (root == nullptr) {
            return;
        }
        result.push_back(root->val); // 将当前节点的值加入结果数组
        preorder(root->left, result); // 递归遍历左子树
        preorder(root->right, result); // 递归遍历右子树
    }
};

// 创建二叉树
TreeNode* createTree() {
    TreeNode* root = new TreeNode(1);
    root->right = new TreeNode(2);
    root->right->left = new TreeNode(3);
    return root;
}

// 打印结果
void printResult(const vector<int>& result) {
    cout << "前序遍历结果：";
    for (int val : result) {
        cout << val << " ";
    }
    cout << endl;
}

int main() {
    Solution sol;
    TreeNode* root = createTree();
    vector<int> result = sol.preorderTraversal(root);
    printResult(result);
    return 0;
}

迭代

cpp

#include <iostream>
#include <vector>
#include <stack>

using namespace std;

// 二叉树节点的定义
struct TreeNode {
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};

// 非递归前序遍历
vector<int> preorderTraversal(TreeNode* root) {
    vector<int> result; // 存储遍历结果的数组
    if (!root) return result; // 如果根节点为空，直接返回空数组

    stack<TreeNode*> st; // 辅助栈，用于存储遍历过程中的节点
    st.push(root); // 将根节点入栈

    while (!st.empty()) { // 当栈非空时循环执行以下操作
        TreeNode* node = st.top(); // 获取栈顶节点
        st.pop(); // 弹出栈顶节点
        result.push_back(node->val); // 将节点值加入结果数组

        if (node->right) { // 如果节点有右子节点，将右子节点入栈
            st.push(node->right);
        }
        if (node->left) { // 如果节点有左子节点，将左子节点入栈
            st.push(node->left);
        }
    }

    return result; // 返回结果数组
}

// 创建二叉树
TreeNode* createTree(vector<int>& nodes, int index) {
    if (index >= nodes.size() || nodes[index] == -1) {
        return nullptr; // 如果节点为空，则返回nullptr
    }
    TreeNode* root = new TreeNode(nodes[index]); // 创建当前节点
    root->left = createTree(nodes, 2 * index + 1); // 创建左子树
    root->right = createTree(nodes, 2 * index + 2); // 创建右子树
    return root; // 返回当前节点
}

// 销毁二叉树
void destroyTree(TreeNode* root) {
    if (!root) return; // 如果根节点为空，直接返回
    destroyTree(root->left); // 递归销毁左子树
    destroyTree(root->right); // 递归销毁右子树
    delete root; // 删除当前节点
}

int main() {
    vector<int> nodes = {1, 2, 3, -1, -1, 4, 5}; // 定义二叉树的先序遍历序列
    TreeNode* root = createTree(nodes, 0); // 创建二叉树
    vector<int> result = preorderTraversal(root); // 进行非递归前序遍历
    for (int val : result) { // 输出遍历结果
        cout << val << " ";
    }
    cout << endl;

    destroyTree(root); // 销毁二叉树

    return 0;
}

Java

java

import java.util.*;

// 二叉树节点的定义
class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode(int x) { val = x; }
}

public class Main {
    // 非递归前序遍历
    public List<Integer> preorderTraversal(TreeNode root) {
        List<Integer> result = new ArrayList<>(); // 存储遍历结果的数组
        if (root == null) return result; // 如果根节点为空，直接返回空数组

        Stack<TreeNode> stack = new Stack<>(); // 辅助栈，用于存储遍历过程中的节点
        stack.push(root); // 将根节点入栈

        while (!stack.isEmpty()) { // 当栈非空时循环执行以下操作
            TreeNode node = stack.pop(); // 获取栈顶节点
            result.add(node.val); // 将节点值加入结果数组

            if (node.right != null) { // 如果节点有右子节点，将右子节点入栈
                stack.push(node.right);
            }
            if (node.left != null) { // 如果节点有左子节点，将左子节点入栈
                stack.push(node.left);
            }
        }

        return result; // 返回结果数组
    }

    // 创建二叉树
    public TreeNode createTree(int[] nodes, int index) {
        if (index >= nodes.length || nodes[index] == -1) {
            return null; // 如果节点为空，则返回null
        }
        TreeNode root = new TreeNode(nodes[index]); // 创建当前节点
        root.left = createTree(nodes, 2 * index + 1); // 创建左子树
        root.right = createTree(nodes, 2 * index + 2); // 创建右子树
        return root; // 返回当前节点
    }

    // 销毁二叉树
    public void destroyTree(TreeNode root) {
        if (root == null) return; // 如果根节点为空，直接返回
        destroyTree(root.left); // 递归销毁左子树
        destroyTree(root.right); // 递归销毁右子树
    }

    public static void main(String[] args) {
        Main solution = new Main();
        int[] nodes = {1, 2, 3, -1, -1, 4, 5}; // 定义二叉树的先序遍历序列
        TreeNode root = solution.createTree(nodes, 0); // 创建二叉树
        List<Integer> result = solution.preorderTraversal(root); // 进行非递归前序遍历
        for (int val : result) { // 输出遍历结果
            System.out.print(val + " ");
        }
        System.out.println();

        solution.destroyTree(root); // 销毁二叉树
    }
}

Python

python

# 二叉树节点的定义
class TreeNode:
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None

# 非递归前序遍历
def preorderTraversal(root):
    result = [] # 存储遍历结果的数组
    if not root:
        return result # 如果根节点为空，直接返回空数组

    stack = [] # 辅助栈，用于存储遍历过程中的节点
    stack.append(root) # 将根节点入栈

    while stack: # 当栈非空时循环执行以下操作
        node = stack.pop() # 获取栈顶节点
        result.append(node.val) # 将节点值加入结果数组

        if node.right: # 如果节点有右子节点，将右子节点入栈
            stack.append(node.right)
        if node.left: # 如果节点有左子节点，将左子节点入栈
            stack.append(node.left)

    return result # 返回结果数组

# 创建二叉树
def createTree(nodes, index):
    if index >= len(nodes) or nodes[index] == -1:
        return None # 如果节点为空，则返回None
    root = TreeNode(nodes[index]) # 创建当前节点
    root.left = createTree(nodes, 2 * index + 1) # 创建左子树
    root.right = createTree(nodes, 2 * index + 2) # 创建右子树
    return root # 返回当前节点

# 销毁二叉树
def destroyTree(root):
    if not root:
        return # 如果根节点为空，直接返回
    destroyTree(root.left) # 递归销毁左子树
    destroyTree(root.right) # 递归销毁右子树

# 主函数
if __name__ == "__main__":
    nodes = [1, 2, 3, -1, -1, 4, 5] # 定义二叉树的先序遍历序列
    root = createTree(nodes, 0) # 创建二叉树
    result = preorderTraversal(root) # 进行非递归前序遍历
    print(result) # 输出遍历结果

    destroyTree(root) # 销毁二叉树

微服务

文档

基础

面试经典算法题20-二叉树的前序遍历 ​

问题描述 ​

思路 ​

递归 ​

迭代 ​

图解 ​

参考代码 ​

C++ ​

递归 ​

迭代 ​

Java ​

Python ​

面试经典算法题20-二叉树的前序遍历

问题描述

思路

递归

迭代

图解

参考代码

C++

递归

迭代

Java

Python