如何实现二叉树所有路径打印？含根到叶及叶到叶路径

你已经搞定了根到叶的路径打印，现在要实现叶到叶路径甚至扩展到所有可能的节点间路径，对吧？我给你用Python和Java分别写了新手友好的代码，先理清楚思路再看代码，保证你能看懂。

核心思路 #

树里没有环，任意两个节点之间只有一条唯一路径。我们可以通过「遍历每个节点作为起点，深度优先搜索（DFS）遍历所有可达节点」的方式，生成所有符合要求的路径——这样既可以覆盖叶到叶路径，也能输出根到叶、中间节点到其他节点的路径，完美匹配你给出的示例输出。

Python 实现 #

1. 定义二叉树节点类

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

2. 构建题目中的二叉树

root = TreeNode(6)
root.left = TreeNode(4)
root.right = TreeNode(0)
root.left.left = TreeNode(1)
root.left.right = TreeNode(3)
root.right.right = TreeNode(1)

3. 核心功能代码

def collect_all_nodes(root):
    """用BFS收集树中所有节点，方便后续遍历每个节点作为路径起点"""
    nodes = []
    queue = [root]
    while queue:
        node = queue.pop(0)
        nodes.append(node)
        if node.left:
            queue.append(node.left)
        if node.right:
            queue.append(node.right)
    return nodes

def dfs(start_node, current_path, result):
    """DFS生成以start_node为起点的所有路径"""
    # 遍历当前节点的左右子节点
    for child in [start_node.left, start_node.right]:
        if child:
            # 生成新路径并加入结果
            new_path = current_path + [child.val]
            result.append(new_path)
            # 递归遍历子节点，延伸路径
            dfs(child, new_path, result)

def print_all_paths(root):
    all_nodes = collect_all_nodes(root)
    all_paths = []
    
    # 遍历每个节点作为路径起点
    for node in all_nodes:
        start_path = [node.val]
        dfs(node, start_path, all_paths)
    
    # 将路径转为逗号分隔的字符串并打印
    for path in all_paths:
        print(','.join(map(str, path)))

4. 运行测试

if __name__ == "__main__":
    print_all_paths(root)

运行后会输出你示例中的所有路径，比如6,4,1、1,4,6,0,1、4,6,0等。

仅输出叶到叶路径的优化 #

如果只需要叶到叶的路径，可以添加一个判断叶子节点的辅助函数，过滤结果：

def is_leaf(node):
    return node.left is None and node.right is None

# 在print_all_paths的打印部分修改：
node_map = {node.val: node for node in all_nodes}
for path in all_paths:
    start_node = node_map[path[0]]
    end_node = node_map[path[-1]]
    if is_leaf(start_node) and is_leaf(end_node):
        print(','.join(map(str, path)))

Java 实现 #

思路和Python完全一致，语法不同而已：

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode(int x) { val = x; }
}

public class BinaryTreePaths {
    public static List<TreeNode> collectAllNodes(TreeNode root) {
        List<TreeNode> nodes = new ArrayList<>();
        Queue<TreeNode> queue = new LinkedList<>();
        queue.add(root);
        while (!queue.isEmpty()) {
            TreeNode node = queue.poll();
            nodes.add(node);
            if (node.left != null) queue.add(node.left);
            if (node.right != null) queue.add(node.right);
        }
        return nodes;
    }

    public static void dfs(TreeNode startNode, List<Integer> currentPath, List<List<Integer>> result) {
        if (startNode.left != null) {
            List<Integer> newPath = new ArrayList<>(currentPath);
            newPath.add(startNode.left.val);
            result.add(newPath);
            dfs(startNode.left, newPath, result);
        }
        if (startNode.right != null) {
            List<Integer> newPath = new ArrayList<>(currentPath);
            newPath.add(startNode.right.val);
            result.add(newPath);
            dfs(startNode.right, newPath, result);
        }
    }

    public static void printAllPaths(TreeNode root) {
        List<TreeNode> allNodes = collectAllNodes(root);
        List<List<Integer>> allPaths = new ArrayList<>();
        
        for (TreeNode node : allNodes) {
            List<Integer> startPath = new ArrayList<>();
            startPath.add(node.val);
            dfs(node, startPath, allPaths);
        }

        // 打印所有路径
        for (List<Integer> path : allPaths) {
            StringBuilder sb = new StringBuilder();
            for (int i = 0; i < path.size(); i++) {
                if (i > 0) sb.append(",");
                sb.append(path.get(i));
            }
            System.out.println(sb.toString());
        }
    }

    public static void main(String[] args) {
        // 构建题目中的二叉树
        TreeNode root = new TreeNode(6);
        root.left = new TreeNode(4);
        root.right = new TreeNode(0);
        root.left.left = new TreeNode(1);
        root.left.right = new TreeNode(3);
        root.right.right = new TreeNode(1);

        printAllPaths(root);
    }
}

内容的提问来源于stack exchange，提问作者user9436638