深度优先搜索查找二叉树的最大深度

Question

我正在解决一个 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;
}

这个解决方案的问题在于有太多的额外空间。是否有一种优化方法？可能Morris遍历的思想在这里会有所帮助？

- St.Antario

---

有多少额外的空间？这里的空间复杂度是O(n)吗？可能并不像你想象的那么多，或者可以忽略不计。 - OscarRyz

Answer 1

在我看来，这里没有太多的空间“浪费”，不确定为什么你要优化这个。你可以尝试的方法是，在 TreeNode 类中添加一个 depth 字段。这应该可以消除使用 depths 数组的需要，并且避免在额外的数组上调用 push/pop 操作。

- Abhinav Mathur