LeetCode--二叉树的最大深度

你的名字 2022-03-06 16:54 247阅读 0赞

题干：

给定一个二叉树，找出其最大深度。

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

**说明:** 叶子节点是指没有子节点的节点。

**示例：**  
给定二叉树 `[3,9,20,null,null,15,7]`，

3
       / \
      9  20
        /  \
       15   7

返回它的最大深度 3 。

解答一（递归实现）：

/**
     * Definition for a binary tree node.
     * public class TreeNode {
     *     int val;
     *     TreeNode left;
     *     TreeNode right;
     *     TreeNode(int x) { val = x; }
     * }
     */
    class Solution {
        public int maxDepth(TreeNode root) {
            if (root == null) {
              return 0;
            } else {
              int left_height = maxDepth(root.left);
              int right_height = maxDepth(root.right);
              return java.lang.Math.max(left_height, right_height) + 1;
            }
        }
    }

解答二（非递归实现）：

/**
     * Definition for a binary tree node.
     * public class TreeNode {
     *     int val;
     *     TreeNode left;
     *     TreeNode right;
     *     TreeNode(int x) { val = x; }
     * }
     */
    public static int maxDepth(TreeNode root) {
            if (root == null) {
                return 0;
            }
            Queue<TreeNode> q = new LinkedList<>();
            q.offer(root);
            int preCount = 1;
            int pCount = 0;
    
            int level = 0;
    
            while (!q.isEmpty()) {
                TreeNode temp = q.poll();
                preCount--;
    
                if (temp.left != null) {
                    q.offer(temp.left);
                    pCount++;
                }
                if (temp.right != null) {
                    q.offer(temp.right);
                    pCount++;
                }
    
                if (preCount == 0) {
                    preCount = pCount;
                    pCount = 0;
                    // System.out.println();
                    level++;
                }
            }
            return level;
        }

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0ZvbGxvd18yNA_size_16_color_FFFFFF_t_70][] 同名原创公众号： **程序大视界**

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0ZvbGxvd18yNA_size_16_color_FFFFFF_t_70]: /images/20220302/8cc5a782846e4341bfa02f97e181a5a1.png