哪吒大战二叉树：递归的奇妙冒险

大家好，我是哪吒，今天我要带你们进入一个神奇的世界——二叉树！别担心，虽然我平时喜欢打打杀杀，但这次我们要用递归来解决二叉树的问题。相信我，这比打妖怪有趣多了！

1. 二叉树的最大深度：哪吒的“高度”挑战

首先，我们来看看如何计算二叉树的最大深度。想象一下，二叉树就像一座塔，我们要找到这座塔的最高点。

Java版

public int maxDepth(TreeNode root) {
    if (root == null) {
        return 0;
    }
    return Math.max(maxDepth(root.left), maxDepth(root.right)) + 1;
}

C++版

int maxDepth(TreeNode* root) {
    if (root == nullptr) {
        return 0;
    }
    return max(maxDepth(root->left), maxDepth(root->right)) + 1;
}

哪吒解说：

• 如果树是空的（root == null），那高度当然是0啦，就像一座空塔。
• 否则，我们分别计算左子树和右子树的高度，然后取最大值，再加上当前节点的高度1。

思考题：

如果二叉树是一个链表（所有节点都只有左子节点或右子节点），最大深度会是多少？

2. 翻转二叉树：哪吒的“镜像”大法

接下来，我们要翻转二叉树。这就像照镜子一样，左右互换。

Java版

public TreeNode invertTree(TreeNode root) {
    if (root == null) {
        return root;
    }
    TreeNode left = root.left;
    root.left = root.right;
    root.right = left;

    invertTree(root.left);
    invertTree(root.right);
    return root;
}

C++版

TreeNode* invertTree(TreeNode* root) {
    if (root == nullptr) {
        return root;
    }
    TreeNode* left = root->left;
    root->left = root->right;
    root->right = left;

    invertTree(root->left);
    invertTree(root->right);
    return root;
}

哪吒解说：

• 如果树是空的，直接返回。
• 否则，我们先交换当前节点的左右子节点，然后递归地对左右子树进行同样的操作。

思考题：

如果二叉树是一个满二叉树（所有非叶子节点都有两个子节点），翻转后会变成什么样子？

3. 对称二叉树：哪吒的“对称”考验

现在，我们要判断一棵二叉树是否对称。这就像看一幅画，左右两边是否完全一样。

Java版

public boolean isSymmetric(TreeNode root) {
    return isSymmetric(root.left, root.right);
}

public boolean isSymmetric(TreeNode node1, TreeNode node2) {
    if (node1 == null && node2 == null) {
        return true;
    }
    if (node1 == null || node2 == null) {
        return false;
    }

    if (node1.val != node2.val) {
        return false;
    }
    return isSymmetric(node1.left, node2.right) && isSymmetric(node1.right, node2.left);
}

C++版

bool isSymmetric(TreeNode* root) {
    if (root == nullptr) {
        return true;
    }
    return isSymmetric(root->left, root->right);
}

bool isSymmetric(TreeNode* node1, TreeNode* node2) {
    if (node1 == nullptr && node2 == nullptr) {
        return true;
    }

    if (node1 == nullptr || node2 == nullptr) {
        return false;
    }

    if (node1->val != node2->val) {
        return false;
    }
    return isSymmetric(node1->left, node2->right) &&
           isSymmetric(node1->right, node2->left);
}

哪吒解说：

• 如果两个节点都为空，那它们是对称的。
• 如果只有一个节点为空，那就不对称。
• 如果两个节点的值不相等，那也不对称。
• 最后，递归地检查左子树的左节点和右子树的右节点，以及左子树的右节点和右子树的左节点。

思考题：

如果二叉树是一个完全二叉树（除了最后一层，其他层都是满的，并且最后一层的节点都靠左），它是否一定是对称的？

4. 二叉树的最近公共祖先：哪吒的“寻亲”之旅

最后，我们要找到二叉树中两个节点的最近公共祖先。这就像在家族树中找到一个共同的祖先。

Java版

public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
    if (root == null || root == q || root == p) {
        return root;
    }

    TreeNode left = lowestCommonAncestor(root.left, p, q);
    TreeNode right = lowestCommonAncestor(root.right, p, q);

    if (left == null) {
        return right;
    }
    if (right == null) {
        return left;
    }
    return root;
}

C++版

TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
    if (root == nullptr || root == q || root == p) {
        return root;
    }

    TreeNode* left = lowestCommonAncestor(root->left, p, q);
    TreeNode* right = lowestCommonAncestor(root->right, p, q);

    if (left == nullptr) {
        return right;
    }
    if (right == nullptr) {
        return left;
    }
    return root;
}

哪吒解说：

• 如果当前节点是空，或者就是我们要找的节点之一，直接返回当前节点。
• 否则，我们分别在左子树和右子树中寻找这两个节点。
• 如果左子树中没有找到，那最近公共祖先就在右子树中。
• 如果右子树中没有找到，那最近公共祖先就在左子树中。
• 如果两个子树都找到了，那当前节点就是最近公共祖先。

思考题：

如果二叉树是一个二叉搜索树（BST），最近公共祖先的查找会有什么不同？

结语：坚持的意义

通过这次冒险，我们不仅学会了如何用递归解决二叉树的问题，还发现了递归的美妙之处。递归就像哪吒的“三头六臂”，虽然看起来复杂，但一旦掌握，就能轻松应对各种挑战。

坚持的意义在于，每一次的递归调用，都是对问题的一次分解和简化。只要我们坚持不懈，最终总能找到问题的答案。就像哪吒一样，无论面对多么强大的敌人，只要坚持战斗，最终总能取得胜利。

希望你们喜欢这次冒险，下次再见！