二叉树的最大深度

[PisecesPeng]

二叉树的最大深度

给定一个二叉树, 找出其最大深度.
二叉树的深度为根节点到最远叶子节点的最长路径上的节点数.

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

示例:

给定二叉树[3,9,20,null,null,15,7]

    3
   / \
  9  20
    /  \
   15   7

返回它的最大深度3.

题目地址: https://leetcode-cn.com/problems/maximum-depth-of-binary-tree/

[PisecesPeng]

解题思路

• 深度优先算法, 递归找到层数最深的节点.

代码

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode() { }
    TreeNode(int val) { this.val = val; }
}

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

[PisecesPeng]

LeetCode题解

解题思路

• 广度优先算法,
• 将每层的节点暂时存放在队列中,
• 且不断推出该节点与推入该节点的子节点们(如果存在的话),
• 以上循环, 记录循环次数.

代码

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode() { }
    TreeNode(int val) { this.val = val; }
}

public static int func(TreeNode root) {
    if (root == null) {
        return 0;
    }
    Queue<TreeNode> queue = new LinkedList<TreeNode>();
    queue.offer(root);
    int ans = 0;
    while (!queue.isEmpty()) {
        int size = queue.size();
        while (size > 0) {
            TreeNode node = queue.poll();
            if (node.left != null) {
                queue.offer(node.left);
            }
            if (node.right != null) {
                queue.offer(node.right);
            }
            size--;
        }
        ans++;
    }
    return ans;
}