【LeetCode 热题 100】226. 翻转二叉树——DFS

Problem: 226. 翻转二叉树
题目：给你一棵二叉树的根节点 root ，翻转这棵二叉树，并返回其根节点。

整体思路

这段代码旨在解决一个非常经典的树操作问题：翻转二叉树 (Invert Binary Tree)。问题要求将一个二叉树的左右子树进行镜像翻转。

该实现采用了一种清晰的 深度优先搜索 (DFS) 的递归方法。其核心思想是，要翻转一棵树，我们只需要先翻转它的左子树和右子树，然后再交换它自己的左右子节点即可。这是一种典型的“后序遍历”应用。

1. 递归函数设计 dfs(node):

   • 这个函数的作用是原地翻转以 node 为根的子树。它没有返回值，因为它直接修改了传入的 node 的 left 和 right 指针。

2. 递归的终止条件 (Base Case)：

   • if (node == null)：如果当前节点为空，说明到达了树的末端，无需任何操作，直接返回。

3. 递归的递推关系 (Recursive Step)：

   • dfs(node.left);：首先，递归地调用 dfs 函数去翻转当前节点 node 的整个左子树。
   • dfs(node.right);：然后，递归地调用 dfs 函数去翻转当前节点 node 的整个右子树。
   • 交换左右子节点：当左右子树都已经被内部翻转完毕后，最后一步就是交换 node 自己的左右孩子指针。
     • TreeNode left = node.left;：用一个临时变量 left 存下原来的左子节点。
     • node.left = node.right;：将 node 的左孩子指向原来的右孩子。
     • node.right = left;：将 node 的右孩子指向原来暂存的左孩子。

通过这种方式，递归从叶子节点开始，层层向上返回，每一层都将自己的左右孩子交换，最终完成了整棵树的镜像翻转。

完整代码

/*** Definition for a binary tree node.* public class TreeNode {*     int val;*     TreeNode left;*     TreeNode right;*     TreeNode() {}*     TreeNode(int val) { this.val = val; }*     TreeNode(int val, TreeNode left, TreeNode right) {*         this.val = val;*         this.left = left;*         this.right = right;*     }* }*/
class Solution {/*** 翻转一棵二叉树。* @param root 二叉树的根节点* @return 翻转后的二叉树的根节点*/public TreeNode invertTree(TreeNode root) {// 调用递归辅助函数进行原地翻转dfs(root);// 返回原始的根节点，此时其结构已被修改return root;}/*** 深度优先搜索（DFS）的递归辅助函数，用于原地翻转以 node 为根的子树。* @param node 当前子树的根节点*/private void dfs(TreeNode node) {// 递归终止条件：如果节点为空，则无需操作。if (node == null) {return;}// 步骤 1: 递归地翻转左子树dfs(node.left);// 步骤 2: 递归地翻转右子树dfs(node.right);// 步骤 3: 交换当前节点的左右子节点TreeNode left = node.left;node.left = node.right;node.right = left;}
}

时空复杂度

时间复杂度：O(N)

1. 节点访问：在整个递归过程中，每个节点都会被访问一次。当访问一个节点时，会执行一些常数时间的操作（检查是否为null，交换指针，进行两次递归调用）。
2. 综合分析：
   • 算法的总时间消耗与树中的节点数量 N 成正比。
   • 因此，时间复杂度为 O(N)。

空间复杂度：O(H)，最坏情况 O(N)

1. 主要存储开销：该算法是原地修改的，其额外空间开销主要来自 递归调用栈 (Call Stack)。递归的深度取决于树的高度 H。

2. 递归栈深度分析：

   • 对于一个平衡二叉树，树的高度 H 约等于 log N。此时，递归栈的空间复杂度为 O(log N)。
   • 对于一个极不平衡的二叉树（例如，一个链状的树），树的高度 H 可能等于 N。此时，递归栈的空间复杂度会达到 O(N)。

综合分析：
算法的空间复杂度由递归调用栈的深度决定，即树的高度 H。因此，空间复杂度为 O(H)。在最坏情况下（链状树），空间复杂度为 O(N)。