翻转二叉树

题目分析

给定一棵二叉树（以层序遍历的方式输入），要求翻转二叉树，也就是交换每个节点的左右子树。最后输出翻转后二叉树的层序遍历结果。

算法思路

1. 构造二叉树
   根据输入的层序遍历序列构造二叉树。先将第一个元素作为根节点，然后依次利用队列为每个节点分配左右子节点。

2. 翻转二叉树
   可采用递归的方法：对每个节点，先递归翻转左子树和右子树，再交换左右子节点。也可以用迭代方式（利用队列或栈）逐层交换。

3. 层序遍历输出
   翻转后利用队列进行层序遍历，将节点值依次输出即可。

复杂度分析

• 时间复杂度：O(n)，其中 n 为节点数。构造树、翻转树以及层序遍历均需要遍历每个节点一次。
• 空间复杂度：O(n)，主要用于存储二叉树以及队列中可能同时存储部分节点。

Python代码

# 定义二叉树节点
class TreeNode:
    def __init__(self, val):
        self.val = val
        self.left = None
        self.right = None

class Solution:
    # 翻转二叉树的递归方法
    def invertTree(self, root: TreeNode) -> TreeNode:
        if not root:
            return None
        # 递归翻转左右子树
        left_inverted = self.invertTree(root.left)
        right_inverted = self.invertTree(root.right)
        # 交换左右子树
        root.left, root.right = right_inverted, left_inverted
        return root

def build_tree(level_order):
    if not level_order or level_order[0] == 'null':
        return None
    
    root = TreeNode(int(level_order[0]))
    queue = [root]
    i = 1
    while i < len(level_order):
        current = queue.pop(0)
        # 构造左子节点
        if i < len(level_order) and level_order[i] != 'null':
            current.left = TreeNode(int(level_order[i]))
            queue.append(current.left)
        i += 1
        # 构造右子节点
        if i < len(level_order) and level_order[i] != 'null':
            current.right = TreeNode(int(level_order[i]))
            queue.append(current.right)
        i += 1
    return root

if __name__ == "__main__":
    import sys
    from collections import deque
    
    # 读取输入，输入为一行，节点值之间用空格分隔
    line = sys.stdin.read().strip()
    if not line:
        sys.exit(0)
    vals = line.split()
    
    root = build_tree(vals)
  
    # 调用翻转二叉树函数
    sol = Solution()
    inverted_root = sol.invertTree(root)
    
    # 层序遍历翻转后的二叉树并输出结果
    res = []
    queue = deque([inverted_root])
    while queue:
        node = queue.popleft()
        res.append(str(node.val))
        if node.left:
            queue.append(node.left)
        if node.right:
            queue.append(node.right)
    
    print(" ".join(res))

Java代码

import java.util.*;

// 主类
public class Main {
    // 内部 Solution 类封装解题逻辑
    public class Solution {
        // 定义二叉树节点
        public class TreeNode {
            int val;
            TreeNode left;
            TreeNode right;
            TreeNode(int x) {
                val = x;
            }
        }
        
        // 翻转二叉树的递归方法
        public TreeNode invertTree(TreeNode root) {
            if (root == null) {
                return null;
            }
            // 递归翻转左右子树
            TreeNode leftInverted = invertTree(root.left);
            TreeNode rightInverted = invertTree(root.right);
            // 交换左右子树
            root.left = rightInverted;
            root.right = leftInverted;
            return root;
        }
        
        // 根据层次遍历构造二叉树
        public static TreeNode buildTree(String[] tokens) {
            if (tokens.length == 0 || tokens[0].equals("null"))
                return null;
            
            TreeNode root = new TreeNode(Integer.parseInt(tokens[0]));
            Queue<TreeNode> queue = new LinkedList<>();
            queue.offer(root);
            int i = 1;
            while (i < tokens.length) {
                TreeNode current = queue.poll();
                // 构造左子节点
                if (i < tokens.length && !tokens[i].equals("null")) {
                    current.left = new TreeNode(Integer.parseInt(tokens[i]));
                    queue.offer(current.left);
                }
                i++;
                // 构造右子节点
                if (i < tokens.length && !tokens[i].equals("null")) {
                    current.right = new TreeNode(Integer.parseInt(tokens[i]));
                    queue.offer(current.right);
                }
                i++;
            }
            return root;
        }
        
        // 层序遍历二叉树并返回结果字符串
        public String levelOrder(TreeNode root) {
            if (root == null) return "";
            StringBuilder sb = new StringBuilder();
            Queue<TreeNode> queue = new LinkedList<>();
            queue.offer(root);
            while (!queue.isEmpty()) {
                TreeNode cur = queue.poll();
                sb.append(cur.val).append(" ");
                if (cur.left != null) {
                    queue.offer(cur.left);
                }
                if (cur.right != null) {
                    queue.offer(cur.right);
                }
            }
            return sb.toString().trim();
        }
    }
    
    public static void main(String[] args) {
        // 读取输入
        Scanner sc = new Scanner(System.in);
        String line = "";
        if(sc.hasNextLine()){
            line = sc.nextLine().trim();
        }
        sc.close();
        
        if(line.length() == 0) return;
        
        String[] arr = line.split("\\s+");
        Main main = new Main();
        Solution solution = main.new Solution();
        // 构造二叉树
        Solution.TreeNode root = solution.buildTree(arr);
        // 翻转二叉树
        Solution.TreeNode invertedRoot = solution.invertTree(root);
        // 输出翻转后的层序遍历结果
        System.out.println(solution.levelOrder(invertedRoot));
    }
}

C++代码

#include <iostream>
#include <sstream>
#include <queue>
#include <vector>
using namespace std;

// 定义二叉树节点结构体
struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode(int x): val(x), left(nullptr), right(nullptr) {}
};

class Solution {
public:
    // 翻转二叉树的递归方法
    TreeNode* invertTree(TreeNode* root) {
        if (root == nullptr) return nullptr;
        // 递归翻转左右子树
        TreeNode* leftInverted = invertTree(root->left);
        TreeNode* rightInverted = invertTree(root->right);
        // 交换左右子节点
        root->left = rightInverted;
        root->right = leftInverted;
        return root;
    }
};

// 根据层次遍历结果构造二叉树
TreeNode* buildTree(const vector<string>& tokens) {
    if (tokens.empty() || tokens[0] == "null")
        return nullptr;
    
    TreeNode* root = new TreeNode(stoi(tokens[0]));
    queue<TreeNode*> q;
    q.push(root);
    int i = 1;
    while (i < tokens.size()) {
        TreeNode* current = q.front();
        q.pop();
        // 构造左子节点
        if (i < tokens.size() && tokens[i] != "null") {
            current->left = new TreeNode(stoi(tokens[i]));
            q.push(current->left);
        }
        i++;
        // 构造右子节点
        if (i < tokens.size() && tokens[i] != "null") {
            current->right = new TreeNode(stoi(tokens[i]));
            q.push(current->right);
        }
        i++;
    }
    return root;
}

// 层序遍历二叉树并输出结果
void levelOrder(TreeNode* root) {
    if (root == nullptr) return;
    queue<TreeNode*> q;
    q.push(root);
    while (!q.empty()) {
        TreeNode* node = q.front();
        q.pop();
        cout << node->val << " ";
        if (node->left) q.push(node->left);
        if (node->right) q.push(node->right);
    }
}

int main(){
    string line;
    getline(cin, line);
    if(line.empty()) return 0;
    istringstream iss(line);
    vector<int> vals;
    int num;
    while(iss >> num) {
        vals.push_back(num);
    }
    
    // 构造二叉树
    TreeNode* root = buildTree(vals);
    Solution solution;
    // 翻转二叉树
    TreeNode* invertedRoot = solution.invertTree(root);
    // 层序遍历输出结果
    levelOrder(invertedRoot);
    return 0;
}

Leetcode 38.翻转二叉树-原题链接

题目内容

给你一棵二叉树的根节点$root$ ，翻转这棵二叉树，并输出其根节点。

输入描述

一行包含二叉树的序列化数组，节点值之间用空格隔开，空节点用null表示。

输出描述

输出翻转后的二叉树的层序遍历结果。（不包含空节点）

样例1

输入

4 2 7 1 3 6 9

输出

4 7 2 9 6 3 1

样例2

输入

2 1 3

输出

2 3 1

提示

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