二叉树边界遍历代码Bug排查求助：部分测试用例执行失败

你的代码存在多处逻辑错误，导致测试用例执行失败。以下是具体问题和修复方案：

主要问题点 #

1. 左边界逻辑错误

   • 原代码仅在左子节点存在左后代时才添加该节点，忽略了左子节点是非叶子但只有右后代的情况。
   • 递归始终走左子树，未处理左子树为空时需沿右子树走左边界的场景。

2. 右边界逻辑完全错误

   • 错误调用left(root.right, arr)，右边界需要独立遍历，且要从下往上添加节点，不能复用左边界的逻辑。
   • 添加节点的条件判断错误，未正确识别非叶子节点。

3. 叶子节点重复添加

   • 原代码会重复添加根节点（如果根是叶子），因为主方法已经加过一次。

4. 主方法语法错误

   • main是void方法，却尝试返回arr，这会导致编译失败。

修复后的完整代码 #

import java.util.ArrayList;
import java.util.Scanner;

public class BoundaryTraversal {
    static class BinaryTreeNode {
        int data;
        BinaryTreeNode left;
        BinaryTreeNode right;

        BinaryTreeNode(int data) {
            this.data = data;
            left = right = null;
        }
    }

    public static void main(String[] args) {
        ArrayList<Integer> arr = new ArrayList<>();
        Scanner sc = new Scanner(System.in);
        BinaryTreeNode root = takeInput(sc);
        
        if (root == null) {
            System.out.println(arr);
            return;
        }
        
        // 边界遍历顺序：根 → 左边界 → 左子树叶子 → 右子树叶子 → 右边界
        arr.add(root.data);
        traverseLeftBoundary(root.left, arr);
        collectLeaves(root.left, arr);
        collectLeaves(root.right, arr);
        traverseRightBoundary(root.right, arr);
        
        System.out.println(arr);
        sc.close();
    }

    // 判断是否为叶子节点
    private static boolean isLeaf(BinaryTreeNode node) {
        return node != null && node.left == null && node.right == null;
    }

    // 遍历左边界：仅添加非叶子节点，优先走左子树
    private static void traverseLeftBoundary(BinaryTreeNode node, ArrayList<Integer> arr) {
        if (node == null || isLeaf(node)) return;
        
        arr.add(node.data);
        if (node.left != null) {
            traverseLeftBoundary(node.left, arr);
        } else {
            traverseLeftBoundary(node.right, arr);
        }
    }

    // 遍历右边界：先递归再添加节点（实现从下到上），优先走右子树
    private static void traverseRightBoundary(BinaryTreeNode node, ArrayList<Integer> arr) {
        if (node == null || isLeaf(node)) return;
        
        if (node.right != null) {
            traverseRightBoundary(node.right, arr);
        } else {
            traverseRightBoundary(node.left, arr);
        }
        arr.add(node.data);
    }

    // 收集所有叶子节点（左到右顺序）
    private static void collectLeaves(BinaryTreeNode node, ArrayList<Integer> arr) {
        if (node == null) return;
        
        if (isLeaf(node)) {
            arr.add(node.data);
            return;
        }
        collectLeaves(node.left, arr);
        collectLeaves(node.right, arr);
    }

    // 从输入构建二叉树的方法（补充完整，假设原代码已有类似实现）
    private static BinaryTreeNode takeInput(Scanner sc) {
        int val = sc.nextInt();
        if (val == -1) return null;
        
        BinaryTreeNode node = new BinaryTreeNode(val);
        node.left = takeInput(sc);
        node.right = takeInput(sc);
        return node;
    }
}

修复说明 #

• 左边界：只添加非叶子节点，左子树不存在时走右子树，确保覆盖所有左边界节点。
• 右边界：先递归遍历子树再添加当前节点，实现从下往上的顺序，右子树不存在时走左子树。
• 叶子节点：分别遍历左右子树的叶子，避免重复添加根节点，保证左到右的顺序。
• 主方法：修正语法错误，调整遍历顺序符合边界遍历的标准定义。

内容的提问来源于stack exchange，提问作者Ayush Singh Bhadoria