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

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;
}

该解决方案的问题在于存在太多额外空间。有没有办法优化它？也许莫里斯遍历的想法在这里可能会有帮助？

Answer 1

在我看来，这里没有太多空间被“浪费”，不知道你为什么要尝试优化它。您可以尝试的一种方法是depth向TreeNode类添加一个字段。这应该消除使用数组的需要depths，并避免您在额外的数组上调用推送/弹出操作。