二叉树反转递归疑问：为何递归root.left/right会终止而root不会？

我在做反转二叉树的题目时，有个疑问：为什么递归调用root.left或root.right时会自动终止，但直接递归root却无法终止？

我最初写的解法是return self.invertTree(root)，显然需要设置递归终止的基准条件，但当时没想到。而正确解法里只递归遍历左右子节点，递归就自动终止了，这让我很困惑。

正确解法代码如下：

def invertTree(self, root):
        """
        :type root: TreeNode
        :rtype: TreeNode
        """
        # 基准条件
        if root is None:
            return root

        # 交换左右子节点
        placeholder = root.left
        root.left = root.right
        root.right = placeholder
        
        # 这里我搞不懂：为什么调用root.left/root.right会终止，调用root就不行？
        self.invertTree(root.left)
        self.invertTree(root.right)
        return root
        # 我最初写的错误代码：return self.invertTree(root)

解答 #

首先得明确：递归能终止的核心是基准条件if root is None: return root，不管递归什么参数，只有触发这个条件才会停止。

为什么递归root.left/root.right能终止？ #

每次递归调用的是当前节点的左/右子节点，二叉树的结构是有限的，最终一定会遍历到叶子节点的子节点——也就是None。比如叶子节点的left和right都是None，当递归到这些None时，就会触发基准条件，直接返回，不会继续递归下去。整个递归过程是沿着树的分支不断深入，直到碰到空节点，然后逐层回溯，自然就终止了。

为什么直接递归root会无限循环？ #

如果写return self.invertTree(root)，相当于每次调用函数时，又把当前的root原封不动地传进去递归。哪怕有基准条件，只要root不是None，就会一直调用invertTree(root)，永远碰不到None的情况（除非一开始root就是空），这就成了无限递归，根本停不下来。

举个简单例子：假设root是一个非空节点，执行return self.invertTree(root)时，函数会再次调用自己，参数还是同一个root，永远不会触发root is None的条件，递归就会一直跑下去直到栈溢出。

内容的提问来源于stack exchange，提问作者Katsu