翻转二叉树[简单]

落日映苍穹つ 2024-02-19 09:59 61阅读 0赞

优秀博文：[IT-BLOG-CN][]

### 一、题目 ###

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

**示例 1：**

![942d2b801fc24c6ca26414b6b00a09fb.png][]

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

**示例 2：**

![352a0cff661644b7b2f071eb6c043e95.png][]

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

**示例 3：**  
输入：`root = []`  
输出：`[]`

> 树中节点数目范围在`[0, 100]`内  
> `-100 <= Node.val <= 100`

### 二、代码 ###

**思想：** 递归地对树进行遍历，并从叶子节点先开始翻转。如果当前遍历到的节点`root`的左右两棵子树都已经翻转，那么我们只需要交换两棵子树的位置，即可完成以`root`为根节点的整棵子树的翻转。

/**
     * 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) {
        
            // 思想：根据递归的思想，获取左子树和右子树，然后将左右子树进行交换，递归退出的条件是子节点为空的时候
            return overReturn(root);
        }
    
        private TreeNode overReturn(TreeNode root) {
        
            if (root == null) {
        
                return null;
            }
            // 递归左子树
            TreeNode left = overReturn(root.left);
            // 递归右子树
            TreeNode right = overReturn(root.right);
            // 将左右子树进行交换
            root.left = right;
            root.right = left;
            return root;
        }
    }

**时间复杂度：** `O(N)`其中`N`为二叉树节点的数目。我们会遍历二叉树中的每一个节点，对每个节点而言，我们在常数时间内交换其两棵子树。  
**空间复杂度：** `O(N)`使用的空间由递归栈的深度决定，它等于当前节点在二叉树中的高度。在平均情况下，二叉树的高度与节点个数为对数关系，即`O(log⁡N)`。而在最坏情况下，树形成链状，空间复杂度为`O(N)`。

[IT-BLOG-CN]: https://it-blog-cn.com/blogs/algorithm/topic/easy/overreturn_tree.html
[942d2b801fc24c6ca26414b6b00a09fb.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/02/19/a1d362c83fd24eb68308c54b13439f5e.png
[352a0cff661644b7b2f071eb6c043e95.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/02/19/2a10888676fd44dd9d78bc0ae402f5eb.png