我正在解决以下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 不同,因为它只在堆栈上保留未访问的节点。
有没有办法改进部分和/或整体实施?
我无法推理您的代码的正确性。
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
用于一对,您可以使用其他一些对/元组)。