LeetCode二叉树路径问题：迭代解法优化问询

你的核心问题在于仅用栈存储节点，导致回溯时需要反向拼接路径，逻辑绕且可读性差。其实迭代DFS可以让栈同时保存当前节点和从根到该节点的路径字符串，这样每一步都能直接维护路径，到叶子节点时直接把路径加入结果即可，回溯逻辑也会简洁很多。

优化后的实现代码 #

import java.util.ArrayList;
import java.util.Deque;
import java.util.ArrayDeque;
import java.util.List;

public class Solution {
    public static List<String> binaryTreePaths(TreeNode root) {
        List<String> result = new ArrayList<>();
        if (root == null) {
            return result;
        }
        // 栈中每个元素存储当前节点和对应的路径字符串
        Deque<Object[]> stack = new ArrayDeque<>();
        stack.push(new Object[]{root, String.valueOf(root.val)});

        while (!stack.isEmpty()) {
            Object[] curr = stack.pop();
            TreeNode node = (TreeNode) curr[0];
            String path = (String) curr[1];

            // 叶子节点，直接加入结果集
            if (node.left == null && node.right == null) {
                result.add(path);
                continue;
            }

            // 先压右节点再压左节点，保证DFS左优先的遍历顺序
            if (node.right != null) {
                stack.push(new Object[]{node.right, path + "->" + node.right.val});
            }
            if (node.left != null) {
                stack.push(new Object[]{node.left, path + "->" + node.left.val});
            }
        }
        return result;
    }

    // 辅助TreeNode类（LeetCode题目中已定义）
    static class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;
        TreeNode() {}
        TreeNode(int val) { this.val = val; }
        TreeNode(int val, TreeNode left, TreeNode right) {
            this.val = val;
            this.left = left;
            this.right = right;
        }
    }
}

优化点说明 #

• 栈元素设计：用数组同时存储节点和路径，避免了回溯时重新拼接路径的麻烦，每一步都能直接拿到当前完整路径。如果觉得数组不够直观，也可以自定义一个简单的Pair类替代：

  static class NodePathPair {
      TreeNode node;
      String path;
      NodePathPair(TreeNode node, String path) {
          this.node = node;
          this.path = path;
      }
  }
  

  之后将栈类型改为Deque<NodePathPair>，代码可读性会进一步提升。
• 逻辑简化：不需要复杂的回溯判断，弹出栈元素后直接判断是否为叶子节点，是则加入结果；否则将左右子节点（注意顺序保证左优先）和拼接后的路径压入栈即可。
• 可读性提升：整个流程和递归逻辑高度对应，没有原代码中反向栈、循环回溯的复杂逻辑，理解成本低。

测试验证 #

用示例输入root=[1,2,3,null,5]，执行流程如下：

1. 压入(1, "1")
2. 弹出(1, "1")，压入(3, "1->3")，再压入(2, "1->2")
3. 弹出(2, "1->2")，压入(5, "1->2->5")
4. 弹出(5, "1->2->5")，是叶子节点，加入结果
5. 弹出(3, "1->3")，是叶子节点，加入结果
   最终输出["1->2->5","1->3"]，完全符合题目要求。

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