1. 前言

二叉树算法题也是面试中常见的一类题目，相对于链表，二叉树每个节点存在两个指针，结构更为复杂。但是相对于节点中有多个指针的多叉树，双节点的操作相对简洁，所以比较适合在面试中的白板编程。二叉树有一些经典问题，例如判断一颗二叉树是否属于平衡二叉树，将一颗二叉树展开为单链表，求解二叉树的深度，二叉树的前序、中序、后序遍历等。这些题目存在基本的算法模板，本章将探讨求解二叉树深度题目。

2. 二叉树深度

面试官提问：给定一个二叉树根节点，如何求解这棵二叉树最大深度？

题目解析：

求解二叉树深度问题是来源于算法网站LeetCode的经典题目，题目链接：https://leetcode.com/problems/maximum-depth-of-binary-tree/。

首先给出二叉树最大深度的定义：二叉树从根节点到所有叶子节点的最长一条路径。例如下图的二叉树，最大深度路径就是3 -> 20 -> 16以及3 -> 20 -> 8，所以最大深度为2。

求解二叉树问题的通用解法是递归算法，使用递归需要满足三个条件：

（1）初始问题可以拆分为多个子问题；
（2）子问题除了数据量不同，求解思路和初始问题相同；
（3）必须存在递归终止条件。

递归算法的优势是代码简洁，在面试过程中白板编程能容易实现 bug free，所以比较推荐候选人尽量采用递归。

二叉树自身的数据结构也可以通过递归实现，对于根节点以及任何一个中间节点，本质上都是存在两个左右子树指针（叶子节点的子树存在，但为空）。

回到题目，对于任何一个节点，如果我们知道左右子树的深度，那么左右子树深度的最大值加一，就是当前节点的深度，这就是子问题的通用解法。最后，确定递归终止条件：如果我们遍历到了空节点，那么停止搜索，算法的 Java 实现，示例：

class Solution {
    public int maxDepth(TreeNode root) {
      	//主函数入口
        int depth=0;
        depth=calDepth(root, depth);
        return depth;
    }
    
    public int calDepth(TreeNode node, int depth){
      	//递归终止条件：如果到了空节点，直接返回深度
        if(node==null) 
          return depth;
      	//深度+1
        depth++;
      	//返回左右子树的最大深度
        return Math.max(calDepth(node.left, depth), calDepth(node.right,depth));
    }
}

从本题中我们可以抽象得到二叉树问题的常见通用解决方案。

二叉树递归本质上属于深度优先搜索算法，我们定义深度优先搜索的 DFS函数，在 DFS 中首先要给出递归终止条件，常见的终止条件是二叉树的叶子节点或者空节点，其次是对于函数入参根节点的左子树和右子树调用函数，在不同函数之间定义 counter 记录结果值或者中间变量值。

算法的伪代码，示例：

public void Solution(TreeNode root){
  //调用递归函数
	dfs(root,counter);
}

public Object dfs(TreeNode root, Object counter){
	//1. 递归终止判断
	if(...)
		...
	//2. 递归调用
	dfs(root.left, counter_1);
  dfs(root.right, counter_2);
  ...
}

3. 小结

本章节中我们给出了二叉树最大深度的算法解法，候选人在编写代码时需要注意边界条件，完成之后可以通过少数几个节点的简单二叉树验证算法运行是否符合预期。最后，我们给出了二叉树搜索的通用递归解法，对于相似的题目，例如求解二叉树的高度，判断一颗二叉树是否属于平衡二叉树，都可以使用递归。