我要解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 在这里会有所帮助?

推荐答案

在我看来,没有太多的空间被"浪费",不知道你为什么要try 优化这个.您可以try 的一种方法是,在TreeNode类中添加一个depth字段.这样就不需要使用depths数组,也不用在额外的数组上调用push/pop操作.

Java相关问答推荐

如何计算内循环的时间复杂度?

R.id.main给我一个红色错误,无法解析MainActivity.java中的符号main

FALSE:它应该在什么时候使用?

获取字符串中带空格的数字和Java中的字符

如何从Keyloak映射Hibernate实体中的用户

Arrays.hashcode(int[])为不同的元素提供相同的散列

虚拟线程应该很快消亡吗?

SpringBoot:在条件{Variable}.isBlank/{Variable}.isEmpty不起作用的情况下进行路径变量验证

Java泛型类方法的静态返回类型是否被类型擦除?

如果List是一个抽象接口,那么Collectors.toList()如何处理流呢?

如何处理两个几乎相同的XSD文件?

为了安全起见,有必要复制一份 list 吗?

如何在Record Java中使用isRecord()和RecordComponent[]?

Java集合:NPE,即使没有添加空值

如何在特定关键字后提取与模式匹配的多个值?

如果c不为null,Arrays.sort(T[]a,Comparator<;?super T>;c)是否会引发ClassCastException?

带有提取器的JavaFXObservableList会根据侦听器的存在而改变行为

可以';不要在Intellij IDEA中使用最新的Java版本(JDK 21)

人们在 IntelliJ 上将-Dhttp.proxyHost=your.proxy.net -Dhttp.proxyPort=8080放在哪里?

移动二维数组的行