求解释二叉树上下翻转问题的递归代码（//1至//5步骤）

先回顾你的示例：原二叉树结构是

1
   / \
  2   3
 / \
4   5

翻转后变成

4
   / \
  5   2
     / \
    3   1

首先先把完整的递归代码补全（你给出的片段缺了后半部分），这样我们能对应着看：

public TreeNode UpsideDownBinaryTree(TreeNode root) {
    if (root == null) return null;
    TreeNode parent = root, left = root.left, right = root.right;
    if (left != null) {
        TreeNode ret = UpsideDownBinaryTree(left); //1
        left.left = right; //2
        left.right = parent; //3
        parent.left = null; //4
        parent.right = null; //5
        return ret;
    }
    // 左子节点为空，说明是最左叶子，作为新根返回
    return root;
}

接下来咱们逐个解释//1到//5的核心逻辑：

• //1：TreeNode ret = UpsideDownBinaryTree(left);
  这一步是递归的「深入阶段」——我们要一直钻到原树的最左叶子节点（也就是示例里的4），因为翻转后这个节点会成为整棵新树的根。递归函数会在到达最左叶子时返回它（因为此时left为null，触发最后一行的return root），而ret就是用来保存这个最终的根节点，后续所有操作都是在给这个根节点构建子树，最后也要把它返回。

• //2：left.left = right;
  这里的left是当前递归层中「原父节点的左孩子」（比如回到处理父节点1的层时，left是2）。根据翻转规则：原父节点的右孩子，会变成原左孩子的左孩子。对应示例里，原父节点1的右孩子是3，翻转后它变成了2的左孩子，这一步就是完成这个赋值。

• //3：left.right = parent;
  同样遵循翻转规则：原父节点，会变成原左孩子的右孩子。对应示例里，原父节点1变成了2的右孩子，这一步就是把这个关系建立起来。

• //4和//5：parent.left = null; + parent.right = null;
  这两步很关键，容易被忽略。原来的父节点（比如1）在翻转后已经变成了新树最底层的叶子节点，它不再需要原来的左右子节点（2和3）。如果不清空这两个指针，会导致树中出现循环引用（比如1的左还是2，而2的右是1，形成环），所以必须把它们置空，保证树的结构是合法的二叉树。

为了更直观，咱们走一遍示例的递归流程：

1. 调用UpsideDownBinaryTree(1)，left是2不为空，递归调用UpsideDownBinaryTree(2)。
2. 调用UpsideDownBinaryTree(2)，left是4不为空，递归调用UpsideDownBinaryTree(4)。
3. 调用UpsideDownBinaryTree(4)，left是null，直接返回4。
4. 回到UpsideDownBinaryTree(2)的层：
   • 把4的左设为5（原2的右孩子），右设为2（原父节点）。
   • 清空2的左右指针（避免循环）。
   • 返回4。
5. 回到UpsideDownBinaryTree(1)的层：
   • 把2的左设为3（原1的右孩子），右设为1（原父节点）。
   • 清空1的左右指针。
   • 返回4，这就是翻转后的根节点。

这样整个翻转过程就完全对应上了，每一层递归都在调整当前左节点的子树关系，最终构建出符合要求的新树。

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