☆打卡算法☆LeetCode 226. 翻转二叉树 算法解析

大家好，我是小魔龙，Unity3D软件工程师，VR、AR，虚拟仿真方向，不定时更新软件开发技巧，生活感悟，觉得有用记得一键三连哦。

一、题目

1、算法题目

“给定一个二叉树的根节点，翻转这颗二叉树，返回其根节点。”

2、题目描述

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

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

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

二、解题

1、思路分析

题意是给定一棵二叉树的根节点，翻转二叉树，返回根节点。

二叉树天生具有递归的性质，从根节点开始，递归地对树进行遍历，并从叶子结点先开始翻转。

如果当前遍历到的节点的左右两颗子树都已经翻转，则需要交换两个子树的位置。

最后遍历完成后，就完成了以root为根节点的整颗子树的翻转。

2、代码实现

代码参考：

class Solution {
    public TreeNode invertTree(TreeNode root) {
        if (root == null) {
            return null;
        }
        TreeNode left = invertTree(root.left);
        TreeNode right = invertTree(root.right);
        root.left = right;
        root.right = left;
        return root;
    }
}

3、时间复杂度

时间复杂度：O(N)

其中N为二叉树节点的数目，遍历二叉树中的每一个节点，对于每个节点而言，只需要在常数时间内交换其两颗子树。

空间复杂度：O(N)

使用的空间由递归栈的深度决定，也就是二叉树的高度，二叉树的高度与节点个数为对数关系，也就是O(log N)，在最坏情况下，树形成链状，空间复杂度为O(N)。

三、总结

如果根节点不为空，那么就要交换其左右子树（即使左右子树是空节点也没关系）。

需要注意的是，当左子树被换位右子树之后，原先的左子树。