226 反转二叉树

一、题目

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

二、题解

2.1 递归

从根节点开始，递归地对树进行遍历，并从叶子节点先开始翻转。如果当前遍历到的节点 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) {
       // 递归终止条件：当前节点为空，直接返回 null
       // 空树翻转后仍然是空树
       if (root == null) {
           return null;
       }

       // 递归翻转右子树
       // 先递归到底，把右子树完全翻转好，返回翻转后的右子树根节点
       TreeNode treeRight = invertTree(root.right);

       // 递归翻转左子树
       // 同样递归到底，把左子树完全翻转好，返回翻转后的左子树根节点
       TreeNode treeLeft = invertTree(root.left);

       // 交换当前节点的左右子树
       // 把翻转后的右子树接到当前节点的左边
       root.left = treeRight;

       // 把翻转后的左子树接到当前节点的右边
       root.right = treeLeft;

       // 返回当前节点（此时它的左右子树已经互换）
       return root;
   }
}

时间复杂度：O(n)O(n)

空间复杂度：O(h)O(h)

评论