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

Question

我正在求解 leetcode problem 以找到二叉树的最大深度。递归解决方案相当简单，因此我尝试实施迭代 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;
}

这个解决方案的问题是有很多额外的space。有没有办法优化它？也许 Morris 遍历的想法在这里可能会有所帮助？

Answer 1

在我看来，这里没有多少 space 被“浪费”，不确定您为什么要尝试优化它。您可以尝试的一种方法是，将 depth 字段添加到 TreeNode class。这应该消除了使用 depths 数组的需要，并且避免了对额外数组调用 push/pop 操作。

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

Depth-first search to find the maximum depth of a binary tree

java

algorithm

binary-tree