leetcode hot100【LeetCode 226. 翻转二叉树】java实现

LeetCode 226. 翻转二叉树

题目描述

翻转一棵二叉树，即将其所有左右子树进行交换。

示例 1：

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

示例 2：

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

示例 3：

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

示例 4：

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

提示：

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

Java 实现解法

方法一：递归

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public TreeNode invertTree(TreeNode root) {
        if (root == null) return null;
        TreeNode temp = root.left;
        root.left = invertTree(root.right);
        root.right = invertTree(temp);
        return root;
    }
}

方法二：迭代

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public TreeNode invertTree(TreeNode root) {
        if (root == null) return null;

        Queue<TreeNode> queue = new LinkedList<>();
        queue.add(root);

        while (!queue.isEmpty()) {
            TreeNode node = queue.poll();

            // 交换当前节点的左右子节点
            TreeNode temp = node.left;
            node.left = node.right;
            node.right = temp;

            // 将左右子节点加入队列
            if (node.left != null) queue.add(node.left);
            if (node.right != null) queue.add(node.right);
        }

        return root;
    }
}

解题思路

方法一：

• 递归方法：
  • 如果当前节点为空，则直接返回 null。
  • 交换当前节点的左右子树。
  • 递归地对左右子树进行相同的操作。

这种方法的时间复杂度是 O(n)，其中 n 是树中节点的数量，因为每个节点恰好被访问一次。空间复杂度是 O(h)，其中 h 是树的高度，这取决于递归调用的栈空间，在最坏情况下（树完全不平衡，如链状结构），空间复杂度为 O(n)。

方法二：

• 层次遍历（广度优先搜索）：
  • 使用一个队列来存储每一层的节点。
  • 如果根节点为空，直接返回 null。
  • 初始化一个队列并将根节点加入队列，然后开始遍历。
  • 在每次迭代中，取出队列中的一个节点，交换其左右子树。
  • 将交换后的左右子树（如果它们不为空）加入队列，以便后续处理。

这种方法的时间复杂度是 O(n)，其中 n 是树中节点的数量，因为每个节点恰好被访问一次。空间复杂度是 O(m)，其中 m 是队列中存储的最大节点数，即树的最大宽度。在最坏情况下，如果树完全不平衡，空间复杂度为 O(n)。