【算法题解】31. 翻转二叉树的递归解法

末蓝、 2024-03-16 10:06 37阅读 0赞

> 这是一道 **简单** 题  
> https://leetcode.cn/problems/invert-binary-tree/

### 题目 ###

给你一棵二叉树的根节点  r o o t root root ，翻转这棵二叉树，并返回其根节点。

示例 1：  
![6f6b7f4d557052f5137b9a880b01f22a.png][]

输入：root = [4,2,7,1,3,6,9] 
    输出：[4,7,2,9,6,3,1]

示例 2：  
![0d6453817420b8025092cc36f4309693.png][]

输入：root = [2,1,3] 
    输出：[2,3,1]

示例 3：

输入：root = [] 
    输出：[]

提示：

*  树中节点数目范围在  \[ 0 , 100 \] \[0, 100\] \[0,100\] 内
 *   − 100 < = N o d e . v a l < = 100 -100 <= Node.val <= 100 −100<=Node.val<=100

### 题解 ###

翻转二叉树，就是交换根结点的左右子节点，而左右子节点同样需要进行翻转，也就是说需要**交换翻转后的左右子节点**。

以Java代码为例：

TreeNode left = root.left;
    TreeNode right = root.right;
    // 交换翻转后的左右子节点
    root.left = invertTree(right);
    root.right = invertTree(left);

以上代码片段明显可以看出使用的是递归的思路。既然使用递归，我们就需要确定递归的三要素：

1.  递归函数：交换根结点的翻转后的左右子节点。
2.  边界条件：根节点为空，无需交换。
3.  还原现场：无需还原。

##### Java 代码实现 #####

/**
     * 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 {
        
        public TreeNode invertTree(TreeNode root) {
        
            if(root == null){
        
                return null;
            }
            TreeNode left = root.left;
            TreeNode right = root.right;
            root.left = invertTree(right);
            root.right = invertTree(left);
            return root;
        }
    }

##### Go 代码实现 #####

/**
     * Definition for a binary tree node.
     * type TreeNode struct {
     *     Val int
     *     Left *TreeNode
     *     Right *TreeNode
     * }
     */
    func invertTree(root *TreeNode) *TreeNode {
        
        
        if root == nil {
        
            return nil
        }
    
        left, right := root.Left, root.Right
    
        root.Left = invertTree(right)
        root.Right = invertTree(left)
    
        return root
        
    }

##### 复杂度分析 #####

*  时间复杂度： O ( n ) O(n) O(n)， n n n为二叉树中节点的个数，每个节点交换子节点的时间复杂度为 O ( 1 ) O(1) O(1)，总共有 n n n个节点，所有总的时间复杂度为 O ( n ) O(n) O(n)。
 *  空间复杂度： O ( n ) O(n) O(n)，空间复杂度为调用栈的深度，最多为 n n n层，即二叉树退化成链表的时候。

[6f6b7f4d557052f5137b9a880b01f22a.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/16/36570b2fd8e448119cd17161cfb0e32f.png
[0d6453817420b8025092cc36f4309693.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/16/56a81d74fb334127843630fc607ca79b.png