面试经典-二叉树最大深度

二叉树最大深度

一、题目

104. 二叉树的最大深度

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

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

示例 1：

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

示例 2：

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

提示：

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

二、题解

深度优先遍历（Depth-First Search, DFS）是一种常用的树或图的遍历算法。它从根节点开始，沿着树的深度方向遍历节点，尽可能深入地访问每个分支，直到无法继续深入为止，然后回溯到上一个节点，继续访问其他未访问的分支

深度优先遍历（Depth-First Search, DFS）包括前序遍历、中序遍历和后序遍历：

• 前序遍历（根节点 -> 左子树 -> 右子树）的结果为：
  • 1 -> 2 -> 4 -> 5 -> 3 -> 6 -> 7
• 中序遍历（左子树 -> 根节点 -> 右子树）的结果为：
  • 4 -> 2 -> 5 -> 1 -> 6 -> 3 -> 7
• 后序遍历（左子树 -> 右子树 -> 根节点）的结果为：
  • 4 -> 5 -> 2 -> 6 -> 7 -> 3 -> 1

广度优先遍历（Breadth-First Search, BFS）也称为层序遍历：

• 层序遍历（从上到下，从左到右）的结果为：
  • 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7

题解一（深度优先，推荐）

// 深度优先
public static int maxDepth(TreeNode root) {
    if (root == null) {
        return 0;
    }
    if (root.left == null && root.right == null) {
        return 1;
    }
    return dfs(root);
}

public static int dfs(TreeNode root) {
    if (root == null) {
        return 0;
    }
    int leftDeep = dfs(root.left);
    int rightDeep = dfs(root.right);
    return Math.max(leftDeep, rightDeep) + 1;
}

题解二（广度优先，不推荐）

// 广度优先
public static int maxDepthFromBFS(TreeNode root) {
    if (root == null) {
        return 0;
    }
    if (root.left == null && root.right == null) {
        return 1;
    }
    int deepth = 0;
    Queue<TreeNode> queue = new LinkedList<>();
    queue.offer(root);
    while (!queue.isEmpty()) {
        int size = queue.size();
        while (size-- > 0) {
            TreeNode pop = queue.poll();
            if (pop != null) {
                if (pop.left != null) {
                    queue.offer(pop.left);
                }
                if (pop.right != null) {
                    queue.offer(pop.right);
                }
            }
        }
        deepth++;
    }
    return deepth;
}

三、总结

package com.loltoulan.binary_tree;

import java.util.LinkedList;
import java.util.Queue;

public class MaxDepth {

    public static void main(String[] args) {
        // TreeNode root = new TreeNode(1);
        // root.left = new TreeNode(2);
        // root.right = new TreeNode(3);
        // root.left.left = new TreeNode(4);
        // root.left.right = new TreeNode(5);
        // root.right.left = new TreeNode(6);
        // root.right.right = new TreeNode(7);
        // root.right.right.right = new TreeNode(7);
        // root.right.right.right.right = new TreeNode(7);
        // root.left.left.left = new TreeNode(8);
        // root.left.left.left.left = new TreeNode(8);
        // System.out.println(maxDepth(root));

        // TreeNode root = new TreeNode(3);
        // root.left = new TreeNode(9);
        // root.right = new TreeNode(20);
        // root.right.left = new TreeNode(15);
        // root.right.right = new TreeNode(7);
        // System.out.println(maxDepth(root));

        TreeNode root = new TreeNode(1);
        root.left = new TreeNode(2);
        root.right = new TreeNode(3);
        root.left.left = new TreeNode(4);
        root.right.right = new TreeNode(5);
        System.out.println(maxDepthFromDFS(root));
    }

    // 广度优先
    public static int maxDepthFromBFS(TreeNode root) {
        if (root == null) {
            return 0;
        }
        if (root.left == null && root.right == null) {
            return 1;
        }
        int deepth = 0;
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        while (!queue.isEmpty()) {
            int size = queue.size();
            while (size-- > 0) {
                TreeNode pop = queue.poll();
                if (pop != null) {
                    if (pop.left != null) {
                        queue.offer(pop.left);
                    }
                    if (pop.right != null) {
                        queue.offer(pop.right);
                    }
                }
            }
            deepth++;
        }
        return deepth;
    }

    // 深度优先
    public static int maxDepthFromDFS(TreeNode root) {
        if (root == null) {
            return 0;
        }
        if (root.left == null && root.right == null) {
            return 1;
        }
        return dfs(root);
    }

    public static int dfs(TreeNode root) {
        if (root == null) {
            return 0;
        }
        int leftDeep = dfs(root.left);
        int rightDeep = dfs(root.right);
        return Math.max(leftDeep, rightDeep) + 1;
    }
}