algorithm - 理解树递归的直观方法-编写代码以检查二叉树是否平衡

问题：
实现一个函数来检查二叉树是否平衡（即否
两个节点与根节点的高度相差超过1）。
解决方案：

int maxDepth(Node *root)
{
   if(!root) return 0;

   return 1 + max(maxDepth(root->left), maxDepth(root->right));
}
int minDepth(Node *root)
{
   if(!root) return 0;

   return 1 + min(minDepth(root->left), minDepth(root->right));
}
bool isBalanced(Node *root)
{
   return maxDepth(root)-minDepth(root) <= 1;
}

有人能帮我理解这个解决方案背后的直觉吗？我正在努力“看到”树算法背后的递归。我知道maxDepth和minDepth应该找到树中最大深度和最小深度的节点的高度，但是我不理解递归是如何工作的。
更重要的是，我不太知道如何自己想出这个解决方案。因此，任何关于如何处理一般树问题的技巧都将非常感谢。

最佳答案

最好的理解方法是看一个例子：

   a
  / \
 b   c
    / \
   d   e

当您在根节点“a”上调用maxDepth时，下面的代码将做什么？

return 1 + max(maxDepth(root->left), maxDepth(root->right));

它将返回1+max ofmaxDepth('b')或maxDepth('c')
maxDepth('b')将返回1，因为：

1 + max( maxDepth(NULL), maxDepth(NULL) ) = 1 + (max (0,0)) = 1 + 0 = 0;

上面从“b”和“b”中分别得到NULLs
所以，回到maxDepth（'a'），现在我们知道它返回：

maxDepth('a') = 1 + max( 1, maxDepth('c'));

maxDepth('c')将遵循相同的步骤并返回2因此：

maxDepth('a') = 1 + max( 1, 2 ) = 1 + 2 = 3

对于mindepth（），流是相同的，唯一的区别是使用min（）而不是max（）。