题解 | #二叉树的前序遍历#

故事背景

想象你有一棵神奇的树，树上的每个节点都有一个数字。我们要做的就是按照一定的顺序记录下每个节点上的数字。这种顺序叫做“前序遍历”。

游戏规则

前序遍历的规则很简单：

1. 先写下当前节点的数字。
2. 然后去看看它的左孩子，如果有左孩子的话，也要按照这个规则写下数字。
3. 接着去看看它的右孩子，如果有右孩子的话，也要按照这个规则写下数字。

示例

让我们通过一个简单的例子来理解这个过程：

示例 1

假设树是这样的：

    1
     \
      2
     /
    3

按照前序遍历的规则，我们应该这样记录：

1. 先写下当前节点 1 的数字。
2. 看看 1 的右孩子 2，先写下 2 的数字。
3. 再看看 2 的左孩子 3，先写下 3 的数字。

最终的结果应该是：[1, 2, 3]

如何实现

我们可以用Java写一个程序来自动完成这个任务。下面是一个简单的实现：

// 定义二叉树节点
class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;

    TreeNode(int x) {
        val = x;
    }
}

public class BinaryTreePreorderTraversal {

    /**
     * 前序遍历
     * @param root 二叉树的根节点
     * @return 节点值的前序遍历结果（作为 int[] 数组）
     */
    public int[] preorderTraversal(TreeNode root) {
        int[] result = new int[100]; // 假设最多有100个节点
        int index = 0; // 当前索引
        fillResult(root, result, index);
        return trimArray(result); // 去掉多余的元素
    }

    /**
     * 填充结果数组
     * @param node 当前节点
     * @param result 结果数组
     * @param index 当前索引
     * @return 下一个索引位置
     */
    private int fillResult(TreeNode node, int[] result, int index) {
        if (node == null) {
            return index;
        }
        
        result[index++] = node.val; // 先写下当前节点的数字
        
        // 去看看它的左孩子
        index = fillResult(node.left, result, index);
        
        // 去看看它的右孩子
        index = fillResult(node.right, result, index);
        
        return index;
    }

    /**
     * 去掉数组中多余的元素
     * @param result 原始数组
     * @return 去掉多余元素后的数组
     */
    private int[] trimArray(int[] result) {
        int count = 0;
        for (int value : result) {
            if (value != 0) {
                count++;
            }
        }
        return Arrays.copyOfRange(result, 0, count);
    }

    
}

解释

1. 定义二叉树节点：
1. 我们定义了一个 TreeNode 类来表示树的节点，每个节点包含一个值 val 和指向左右孩子的指针 left 和 right。
2. 前序遍历方法：
1. preorderTraversal 方法负责整个遍历过程。
2. 初始化一个足够大的数组 result 来存放结果。
3. 使用 fillResult 方法来递归地遍历树，并将节点值填入数组中。
3. 填充结果数组：
1. fillResult 方法负责递归地遍历树，并填充结果数组。
2. 每次访问一个节点时，将节点值存入数组，并更新当前索引的位置。
4. 去掉多余的元素：
1. trimArray 方法用来去掉数组中多余的元素（未使用的部分）。

如果这篇文章对你有帮助，请点个免费的赞👍，让它能帮到更多的人。