⭐️ 题目日期：

华为 - 2024/11/29

🌳 题目描述：

给定一棵二叉树的根节点 root，左右翻转这棵二叉树，即左节点为右节点，右节点为左节点，子树也需要翻转，并返回其根节点。

示例 1：

输入：head = [10, 8, 15, 1, 9, 13, 17]

输出：[10, 15, 8, 17, 13, 9, 1]

解释图例：

🕵🏽 面试评估：

这道题考察候选人是否能根据二叉树的定义实现递归终止条件的设计，并正确设计递归的调用顺序（先处理子树，再操作当前节点）。

🧗难度系数：

⭐️ ⭐️

📝思路分析：

这道题我们使用递归，首先我们需要知道递归的终止条件，当 当前节点 为空时，即返回空

我们开始操作当前节点，保存当前节点的左子树，然后将当前节点的左子树变为翻转后的右子树，将当前节点的右子树变为翻转后的左子树

最后，返回翻转后的当前节点。

如案例所示，在 Step 1，我们处理根节点 10 ，此时当前节点为 10，我们保存它的左子树：temp = root.left，此时为 8，随后，将左子树变为翻转后的右子树 root.left = flipTree(root.right)，即翻转 15；左子树变为翻转后的左子树 root.right = flipTree(temp)，即翻转 8；

我们进入新的递归，处理左子树 15，即 flipTree(root.right)

不断递归，直至当前节点的左子树和右子树均为 null，就直接返回节点。

💻代码：

Java

    public TreeNode flipTree(TreeNode root) {
        if(root == null) {
            return null;
        }
    
        TreeNode temp = root.left;
        root.left = flipTree(root.right);
        root.right = flipTree(temp);
    
        return root;
    }

Python

    def flipTree(self, root):
        if root is None:
            return None
    
        root.left, root.right = self.flipTree(root.right), self.flipTree(root.left)
    
        return root

🚵🏻复杂度分析：

时间复杂度：O(n)，n 为节点的数量

空间复杂度：O(h)，递归栈的最大深度为树的高度。最坏情况为 O(n); 对于完全二叉树为 O(logn)

🔬在线评测(Online Judge):

题目链接