我要解leetcode problem来求二叉树的最大深度.递归解决方案相当简单,所以我try 实现迭代DFS方法.以下是我的 idea :
public class TreeNode {
int val;
TreeNode left;
TreeNode right;
public TreeNode() {}
public TreeNode(int val) { this.val = val; }
public TreeNode(int val, TreeNode left, TreeNode right) {
this.val = val;
this.left = left;
this.right = right;
}
}
public static int maxDepthDfs(TreeNode root){
Deque<TreeNode> stack = new LinkedList<>();
Deque<Integer> depths = new LinkedList<>();
TreeNode current = root;
int maxDepth = 0;
int currentDepth = 0;
while(!stack.isEmpty() || current != null){
if(current == null){
if(currentDepth > maxDepth){
maxDepth = currentDepth;
}
current = stack.pop().right;
currentDepth = depths.pop() + 1;
} else {
stack.push(current);
current = current.left;
depths.push(currentDepth);
currentDepth++;
}
}
return maxDepth;
}
这个解决方案的问题是有太多额外的空间.有没有办法优化它?也许莫里斯·特拉弗斯的 idea 在这里会有所帮助?