LeetCode 104.二叉树的最大深度

题目描述

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

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

示例 1：

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

示例 2：

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

提示：

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

思路

首先需要搞清楚二叉树的深度和高度是什么？

• 二叉树节点的深度：指从根节点到该节点的最长简单路径边的条数或者节点数（取决于深度从0开始还是从1开始）
• 二叉树节点的高度：指从该节点到叶子节点的最长简单路径边的条数或者节点数（取决于高度从0开始还是从1开始）

因此，根节点的高度就是二叉树的最大深度（正因此，本题使用后序遍历来求高度）。本题笔者使用递归法来解决。

递归三部曲：

1. 确定递归函数的参数和返回值。参数就是传入树的根节点，返回就返回这棵树的深度，所以返回值为int类型。
2. 确定终止条件。如果为空节点的话，就返回0，表示高度为0。
3. 确定单层递归的逻辑。本题可以分解为先求左子树和右子树的最大高度，再加上1便是父节点的最大高度的子问题，且子问题与本问题的求解思路相同，只是规模不同，也存在终止条件，这就是本题能够使用递归法解决的关键。

代码

C++版：

/*** Definition for a binary tree node.* struct TreeNode {*     int val;*     TreeNode *left;*     TreeNode *right;*     TreeNode() : val(0), left(nullptr), right(nullptr) {}*     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}*     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}* };*/
class Solution {
public:// 递归法，后序遍历求高度int getHeight(TreeNode* node){if(node==NULL) return 0;int leftHeight=getHeight(node->left); // 左int rightHeight=getHeight(node->right); // 右int height=1+max(leftHeight,rightHeight)// 中return height;}int maxDepth(TreeNode* root) {return getdepth(root);}
};

Python版：

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:# 递归法，后序遍历求高度def getHeight(self, node: Optional[TreeNode]) -> int:if not node:return 0leftheight = self.getHeight(node.left) # 左rightheight = self.getHeight(node.right) # 右height = 1 + max(leftheight, rightheight) # 中return heightdef maxDepth(self, root: Optional[TreeNode]) -> int:return self.getHeight(root)

需要注意的地方

1.二叉树求高度需要使用后序遍历（左右中，从下往上计数+1），求深度需要使用前序遍历（中左右，从上往下计数+1）。

2.本题使用递归法解决的话也可以使用前序遍历，使用迭代法解决的话则使用层序遍历是最为合适的。