leetcode104：二叉树的最大深度

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

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

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

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

返回它的最大深度 3

附赠leetcode地址：leetcode

解答：递归

const maxDepth = function(root) {
    if(!root) return 0 
    return 1 + Math.max(maxDepth(root.left), maxDepth(root.right))
};

复杂度分析：

时间复杂度：O(n)

空间复杂度： O(log⁡n)

leetcode

二叉树的最大深度

主要考察的是深度优先遍历

function TreeDepth(node) {
    // 最大深度等于左子树或者右子树的最大值加1
    return !node ? 0 : Math.max(TreeDepth(node.left), TreeDepth(node.right)) + 1
}

@XuShunyi 你说的没错，节点的深度是这么定义的，但是题干问的是树的最大深度，就是指根节点到最远叶子节点的边的数量，也就是最远的子节点的深度。最远的子节点的深度=树的最大深度

@XuShunyi 是的哦，是有点问题，我找到了另一种定义。

层数：根节点为第一层，往下一次递增。树中节点的最大层数称之为树的深度或者高度
树的高度，深度，层数_Java_Mind And Hand-CSDN博客

分析

根节点如果为空深度为0，如果不为空则深度为1加上左子树的高度或者右子树的高度（取决于左子树和右子树的高度哪个更大）
计算左子树的高度和右子树的高度，取最大值
很明显，递归

var maxDepth = function (root) {
  if (root == null) return 0;
  return 1 + Math.max(maxDepth(root.left), maxDepth(root.right));
};

递归,记录最大长度

function maxTreeCount(root){
      if(!root) return 0
      let max = 1
      TreeCount(root, 1)
      function TreeCount(node, num){
             max= Math.max(max, num++)
             if(node.left)TreeCount(node.left, num)
             if(node.right)TreeCount(node.right, num)
      }
      return max
}

迭代实现
依次循环出栈遍历入栈，直到栈为空，遍历完成
弊端：但每个节点需要记录一个属性，修改了元数据

function maxTreeCount(root){
      if(!root) return 0
      let max = 1
      const stack = [];
      root.index = 1
      stack.push(root)
      while(stack.length>0){
            const curNode = stack.pop()
            max = Math.max(max, curNode.index)
            if(curNode.left){
                  curNode.left.index = curNode.index+1
                  stack.push(curNode.left)
            }
            if(curNode.right){
                  curNode.right.index = curNode.index+1
                  stack.push(curNode.right)
            }
      }
      return max
}

@luweiCN

@luweiCN ,你看下例子里的那棵树，根节点3到叶子节点7的边的数量不是2吗，题中说是3，按你说的好像也不对

二叉树的最大深度指的是包括根节点的呀。从根结点到叶结点依次经过的结点（含根、叶结点）形成树的一条路径，最长路径的长度为树的深度。

BFS

var maxDepth = function(root) {
    if(!root) return 0;
    let max = 0;
    let queue = [root];

    while(queue.length) {
        max+=1;
        let len = queue.length;
        for(let i = 0;i<len; i++) {
            let node = queue.shift();
            if(node.left) queue.push(node.left);
            if(node.right) queue.push(node.right);
        }
    }
    return max;
};

题目地址（104. 二叉树的最大深度）

https://leetcode-cn.com/problems/maximum-depth-of-binary-tree/description/

题目描述

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

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

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

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

    3
   / \
  9  20
    /  \
   15   7
返回它的最大深度 3 。

前置知识

递归

公司

阿里
腾讯
百度
字节
apple
linkedin
uber
yahoo

思路

由于树是一种递归的数据结构，因此用递归去解决的时候往往非常容易，这道题恰巧也是如此，

用递归实现的代码如下：

var maxDepth = function (root) {
  if (!root) return 0;
  if (!root.left && !root.right) return 1;
  return 1 + Math.max(maxDepth(root.left), maxDepth(root.right));
};

如果使用迭代呢？我们首先应该想到的是树的各种遍历，由于我们求的是深度，因此
使用层次遍历（BFS）是非常合适的。我们只需要记录有多少层即可。相关思路请查看binary-tree-traversal

关键点解析

队列
队列中用 Null(一个特殊元素)来划分每层，或者在对每层进行迭代之前保存当前队列元素的个数（即当前层所含元素个数）
树的基本操作- 遍历 - 层次遍历（BFS）

代码

语言支持：JS，C++，Java，Python, Go, PHP

JS Code:

/*
 * @lc app=leetcode id=104 lang=javascript
 *
 * [104] Maximum Depth of Binary Tree
 */
/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
/**
 * @param {TreeNode} root
 * @return {number}
 */
var maxDepth = function (root) {
  if (!root) return 0;
  if (!root.left && !root.right) return 1;

  // 层次遍历 BFS
  let cur = root;
  const queue = [root, null];
  let depth = 1;

  while ((cur = queue.shift()) !== undefined) {
    if (cur === null) {
      // 注意⚠️： 不处理会无限循环，进而堆栈溢出
      if (queue.length === 0) return depth;
      depth++;
      queue.push(null);
      continue;
    }
    const l = cur.left;
    const r = cur.right;

    if (l) queue.push(l);
    if (r) queue.push(r);
  }

  return depth;
};

C++ Code:

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    int maxDepth(TreeNode* root) {
        if (root == nullptr) return 0;
        auto q = vector<TreeNode*>();
        auto d = 0;
        q.push_back(root);
        while (!q.empty())
        {
            ++d;
            auto sz = q.size();
            for (auto i = 0; i < sz; ++i)
            {
                auto t = q.front();
                q.erase(q.begin());
                if (t->left != nullptr) q.push_back(t->left);
                if (t->right != nullptr) q.push_back(t->right);
            }
        }
        return d;
    }
};

Java Code:

/**
 * 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;
        }
        // 队列
        Queue<TreeNode> queue = new LinkedList<TreeNode>();
        queue.offer(root);
        int res = 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-=1;
            }
            // 统计层数
            res +=1;
        }
        return res;
    }
}

Python Code:

class Solution:
    def maxDepth(self, root: TreeNode) -> int:
        if not root: return 0
        q, depth = [root, None], 1
        while q:
            node = q.pop(0)
            if node:
                if node.left: q.append(node.left)
                if node.right: q.append(node.right)
            elif q:
                q.append(None)
                depth += 1
        return depth

Go Code:

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
// BFS
func maxDepth(root *TreeNode) int {
	if root == nil {
		return 0
	}

	depth := 1
	q := []*TreeNode{root, nil} // queue
	var node *TreeNode
	for len(q) > 0 {
		node, q = q[0], q[1:] // pop
		if node != nil {
			if node.Left != nil {
				q = append(q, node.Left)
			}
			if node.Right != nil {
				q = append(q, node.Right)
			}
		} else if len(q) > 0 { // 注意要判断队列是否只有一个 nil
			q = append(q, nil)
			depth++
		}
	}
	return depth
}

PHP Code:

/**
 * Definition for a binary tree node.
 * class TreeNode {
 *     public $val = null;
 *     public $left = null;
 *     public $right = null;
 *     function __construct($value) { $this->val = $value; }
 * }
 */
class Solution
{

    /**
     * @param TreeNode $root
     * @return Integer
     */
    function maxDepth($root)
    {
        if (!$root) return 0;

        $depth = 1;
        $arr = [$root, null];
        while ($arr) {
            /** @var TreeNode $node */
            $node = array_shift($arr);
            if ($node) {
                if ($node->left) array_push($arr, $node->left);
                if ($node->right) array_push($arr, $node->right);
            } elseif ($arr) {
                $depth++;
                array_push($arr, null);
            }
        }
        return $depth;
    }
}

复杂度分析

时间复杂度：$O(N)$
空间复杂度：$O(N)$

Navigation Menu

Repository navigation

leetcode104：二叉树的最大深度 #42

解答：递归

二叉树的最大深度

分析

BFS

题目地址（104. 二叉树的最大深度）

题目描述

前置知识

公司

思路

关键点解析

代码

相关题目

Metadata

Assignees

Labels

Projects

Milestone

Relationships

Development

leetcode104：二叉树的最大深度 #42

Description

Activity

sisterAn commented on May 14, 2020

解答：递归

plane-hjh commented on May 15, 2020

二叉树的最大深度

luweiCN commented on May 15, 2020

luweiCN commented on May 15, 2020

luweiCN commented on May 15, 2020

分析

fanefanes commented on May 15, 2020

plane-hjh commented on May 15, 2020

AnranS commented on Nov 19, 2020

BFS

azl397985856 commented on Mar 3, 2021

题目地址（104. 二叉树的最大深度）

题目描述

前置知识

公司

思路

关键点解析

代码

相关题目

kangkang123269 commented on Feb 23, 2023

Metadata

Metadata

Assignees

Labels

Projects

Milestone

Relationships

Development

Issue actions