我正在解決一個leetcode 問題以找到二叉樹的最大深度。遞回解決方案相當簡單，因此我嘗試實作迭代 DFS 方法。這是我想出的：
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;
}
這個解決方案的問題是有太多的額外空間。有沒有辦法優化它？也許莫里斯遍歷的想法在這里可能會有所幫助？
uj5u.com熱心網友回復：
在我看來，這里沒有多少空間被“浪費”，不知道你為什么要優化它。您可能會嘗試的一種方法是depth向類添加一個欄位TreeNode。這應該消除了使用depths陣列的需要，并使您免于在額外的陣列上呼叫推送/彈出操作。
轉載請註明出處，本文鏈接：https://www.uj5u.com/gongcheng/468471.html
上一篇：奶牛天課計算