首页 计算机学科 java 编程题

# 二叉树最大深度 - 使用非递归后序遍历实现

给定一个二叉树 root ，返回其最大深度。

二叉树的 最大深度 是指从根节点到最远叶子节点的最长路径上的节点数。

示例 1：

img

输入：root = [3,9,20,null,null,15,7]
输出：3

示例 2：

输入：root = [1,null,2]
输出：2

提示：

  • 树中节点的数量在 [0, 104] 区间内。
  • -100 <= Node.val <= 100

# 思路分析：

使用非递归 的 后序遍历 我们需要使用到 栈 将经过的 节点 压入栈中

image-20240128220924192

我们先是 向左走到走并且 将 经过的所有节点都压入栈 中，当回去的时候再不断的将 栈中的元素 弹出

但是我们可以注意一下，从 1 走到 4 走到头了，那么这时栈中元素的个数 就代表着 树 从 1 到 4 它的深度

当然这不是最大深度，如果接下来是从 1 到 7 ，走到 7 可能会是如下图所示的样子：

image-20240128221252821

那么这时我们就需要 将 最大深度 更新一下。

每次如果有更大的值，那么就更新 最大深度的值，等到所有节点都遍历过一遍之后，记录的 最大深度的值 就是 这棵树的最大深度

# 代码实现：

class Solution {
    public int maxDepth(TreeNode root) {
        // 先实现 非递归的后序遍历代码
        TreeNode cur = root;
        // 记录 最近弹出元素
        TreeNode pop = null;
        // 记录 最大深度的值
        int max = 0;
        // 非递归后序遍历我们需要使用到 栈来存储 回去的路
        LinkedList<TreeNode> stack = new LinkedList<>();
        // 如果 cur 不为 null 并且 stack 不为空 就循环
        while(cur != null || ! stack.isEmpty()) {
            // 判断 cur 不为 null 就将 当前 cur 存储到 栈中 记录来时的路
            if(cur != null) {
                stack.push(cur);
                // 判断 最大深度的值 每次更新 max 的值
                if(max < stack.size())
                    max = stack.size();
                // 向左不断走
                cur = cur.left;
            }else {
                // 拿一下 栈顶元素
                TreeNode peek = stack.peek();
                // 判断 来时的上一个元素 的右边是否有节点 并 判断 来时的路的 右边节点是否走过了，走过就不走了不然会死循环 到这
                if(peek.right == null || peek.right == pop)
                    // 没路可走了 并且 右边的孩子也处理过了那么就弹出来时的路回到 上一步 继续下一轮循环
                    pop = stack.pop();
                else
                    // 向右不断走
                    cur = peek.right;
            }
        }
        // 返回最大深度的值
        return max;
    }
}