Leetcode：二叉树路径

Question

我正在解决以下leetcode问题：

给定二叉树的根，返回任意位置的所有根到叶路径 订购。

叶子是没有子节点的节点。

输入：

root

=

[1,2,3,null,5]

输出：

["1->2->5","1->3"]

递归解决方案很简单，所以我尝试提出迭代解决方案。这是我的解决方案的样子：

public static List<String> binaryTreePaths(TreeNode root) {
    List<String> retVal = new ArrayList<>();
    Deque<TreeNode> stack = new ArrayDeque<>();
    while(root != null) {
        if(root.left != null){
            stack.push(root);
            root = root.left;
        } else if (root.right != null) {
            stack.push(root);
            root = root.right;
        //
        //The code under the else branch below is difficult to read
        //
        } else {
            final var arr = new ArrayList<>(stack);
            Collections.reverse(arr);
            arr.add(root);
            final var path = arr.stream()
                    .map(node -> String.valueOf(node.val))
                    .collect(Collectors.joining("->"));
            retVal.add(path);
            TreeNode newRoot = null;
            while(!stack.isEmpty()){
                TreeNode previous = stack.pop();
                TreeNode current = root;
                if(previous.right != null && previous.right != current){
                    stack.push(previous);
                    newRoot = previous.right;
                    break;
                } else {
                    root = previous;
                }
            }
            root = newRoot;
        }
    }
    return retVal;
}

问题：代码相对冗长，难以阅读。我的想法是跟踪从顶部到当前节点的整个路径。但这与标准 DFS 不同，因为它只在堆栈上保留未访问的节点。

有没有办法改进部分和/或整体实施？

Answer 1

我无法推理您的代码的正确性。

root

的移动让我迷路了。为什么不让自己轻松一点，边走边构建琴弦呢？:

public static List<String> binaryTreePaths(TreeNode root) {
    List<String> retVal = new ArrayList<>();
    Stack<AbstractMap.SimpleEntry<TreeNode, String>> stack;
    if (root == null) return retVal;
    stack.push(makePair(root, root.val))
    while(!stack.empty()) {
        AbstractMap.SimpleEntry<TreeNode, String> item = stack.pop();
        TreeNode current = item.getKey();
        if(current.left!=null) {
            stack.push(makePair(current.left,
                item.getValue()+"->"+current.left.val))
        }
        if(current.right!=null) {
            stack.push(makePair(current.right,
                item.getValue()+"->"+current.right.val));
        }
        if(current.left==null && current.right==null) {
            retVal.add(item.getValue());
        }
    }
    return retVal;
}

代码未经测试，可能无法编译，视为伪代码。

makePair

的实现留给读者作为练习（

AbstractMap.SimpleEntry

用于一对，您可以使用其他一些对/元组）。