java - 二叉树的递归代码流程

Question

我试图逐步理解这个递归程序，了解每次调用该函数时会发生什么，但想确定我认为的代码流是否正确。

    public static int checkHeight(TreeNode root) {
        if (root == null) {
            return 0; // Height of 0
        }

        /* Check if left is balanced. */
        int leftHeight = checkHeight(root.left);
        if (leftHeight == -1) {
            return -1; // Not balanced
        }
        /* Check if right is balanced. */
        int rightHeight = checkHeight(root.right);
        if (rightHeight == -1) {
            return -1; // Not balanced
        }

        /* Check if current node is balanced. */
        int heightDiff = leftHeight - rightHeight;
        if (Math.abs(heightDiff) > 1) {
            return -1; // Not balanced
        } else {
            /* Return height */
            return Math.max(leftHeightJ rightHeight) + 1;
        }
    }
    public static boolean isBalanced(TreeNode root)
    {
        if (checkHeight(root) == -1)
        {
            return false;
        }
        else
        {
            return true;
        }
    }

示例:

           1
        /     \
       2       3
    /    \   /
   4      5  6
 /
7

当程序运行并到达 checkHeight(root.left) 行时，它现在的元素为 2(root.left)，因此会递归调用该函数，并且堆栈会暂停执行，如下所示

|checkHeight(2)| 

然后直到到达最左边元素的末尾为止

|checkHeight(7)|
|checkHeight(4)|
|checkHeight(2)|

|检查高度(7)|弹出时 leftHeight = 0 rightHeight = 0。

运行时 |checkHeight(4)| -> 左高度=1，右高度=0

|检查高度(2)| -> leftHeight = 2, rightHeight=1(因为它运行 |checkHeight(5)|)

一旦完成，它会返回:Max(2,1)+1 = 3，这将是 leftHeight 的值。

我的理解正确吗？希望我没有混淆这些步骤。提前致谢

Answer 1

既然你没有问一个可以用代码来回答的具体问题，我可以这样说:

递归的关键不是跟随每一次调用并坚持调用迷宫，而是阅读代码(对于递归调用)并相信递归调用应该做什么，它应该做什么。最好确保单次调用它正在执行的操作的正确性。然后你可以直接跳过所有“相似”的调用直到最后(比如这里的7)

另一件事是基本规则，方法返回必须有一个条件 - 基本情况(防止无限循环)

考虑到这两个事实，我认为您的步骤是正确的(我确实遵循了调用。)

提示:您始终可以在调试中使用断点来检查整个过程，而不是手动检查。毕竟，这就是调试的目的。