大家好我是西瓜哥，今天我们做一道非常经典的二叉树算法题：二叉树的最大深度。
此题难度为简单。
LeetCode 题目链接：https://leetcode-cn.com/problems/maximum-depth-of-binary-tree/
本题本质考察的的是二叉树的递归遍历。
递归
递归（Recursion）指的是 在函数执行中调用函数自身 的行为，这种函数也被称为 递归函数。为了防止无限递归出现死循环，通常我们还会在递归函数中加入退出递归的分支条件。
递归这个名字起得非常传神，“递” + “归”，递过去，然后对方处理好了，然后再拿回来。
递归的例子
举个例子，你在排队，前面有很多人，你想知道前面有几个人。于是你问在排在你前面的人。他也不知道，他先不回答你，也做出了和你一样的动作：问他的前面的人,前面有几个人。
如此递归下去，直到第一个人，他没有前面的人，只好退出递归，回答后面的那个人说，“前面有 0 个人”，然后他后面那个人加上个 1，再对他后面对人说，“前面有 1 个人”。
依此类推，最后你就拿到了结果，知道了前面有几个人。
递归刚接触的时候并不好理解，因为递归的思维模式和我们常规的思维模式不同。
它针对的是局部，当局部实现了自洽，那么整体就是正确的。当我们尝试通过这个局部去了解全貌时，脑中形成的影像是模糊的，尤其是递归逻辑比较复杂的时候。
二叉树的最大深度
二叉树的深度如何求？基本上二叉树的要用到递归的算法题，都是在前序遍历、中序遍历、后续遍历上做一些调整。
function TreeNode(val, left, right) {
this.val = (val===undefined ? 0 : val)
this.left = (left===undefined ? null : left)
this.right = (right===undefined ? null : right)
}
function dfs(root) {
// 前序遍历
dfs(root.left);
// 中序遍历
dfs(root.right);
// 后序遍历
}
其中的后序遍历，就适合处理完当前节点的左子、右子数处理出来的结果，结合当前节点，然后返回一个值。
求二叉树的最大深度，就是对后序编辑做一些改造。
我们先看代码实现：
function maxDepth(root) {
if (root === null) return 0;
return 1 + Math.max(maxDepth(root.left), maxDepth(root.right));
};
这个递归怎么理解？就是对于局部的一棵树来说，我们求左右子树的高度，怎么求，调用递归函数。求完后，取其中大的，然后再加上根节点自己的一层，得出来的值就是这整棵树的最大高度了。
当然我们不能忘记退出递归的条件，就是这个树不存在了，也就是为 null 的时候，返回一个高度 0。
至此解题结束。总的来说，并不难，关键是要充分理解二叉树递归的思想。
网友评论