手撸二叉树之翻转二叉树

题目

翻转一棵二叉树。

示例：

输入：

    4
   /   \
  2     7
 / \   / \
1   3 6   9

输出：

    4
   /   \
  7     2
 / \   / \
9   6 3   1

解题思路

根据题意，翻转二叉树的意思就是把每个节点的左右孩子翻转，这样就可以达到整体的翻转效果了。

所以，我们可以利用先序遍历，中序遍历，后续遍历这三种方法中的一种来实现翻转，思路如下：

递归三部曲：

1. 确定递归函数的参数和返回值：递归函数的参数为输入的节点，由于题目中需要返回 TreeNode 类型的返回值，所以递归函数的返回值为 TreeNode;
2. 确定终止条件：当 root == null 时,终止递归，返回 root;
3. 确定单层递归逻辑: 如果是先序遍历，则先交换左右孩子节点，然后翻转左子树，再翻转右子树；如果是中序遍历，则先翻转左子树，再交换左右孩子节点，最后翻转右子树；如果是后序遍历，则先翻转左子树，再翻转右子树，最后交换左右孩子节点；

代码实现

/**
 * 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) {
            if (root == null) return null;
            // 保存右子树
            TreeNode rightTree = root.right;
            // 交换左右子树的位置
            root.right = invertTree(root.left);
            root.left = invertTree(rightTree);
            return root;
        }
    }

// 利用中序遍历
class Solution {
    public TreeNode invertTree(TreeNode root) {
            if (root == null) return null;
            invertTree(root.left); // 递归找到左节点
            TreeNode rightNode= root.right; // 保存右节点
            root.right = root.left;
            root.left = rightNode;
            // 递归找到右节点 继续交换 : 因为此时左右节点已经交换了,所以此时的右节点为root.left
            invertTree(root.left); 
    }
}

// 利用后序遍历
 class Solution {
        public TreeNode invertTree(TreeNode root) {
            // 后序遍历
            if (root == null) return null;
            TreeNode leftNode = invertTree(root.left);
            TreeNode rightNode = invertTree(root.right);
            root.right = leftNode;
            root.left = rightNode;
            return root;
        }
    }

最后

复杂度分析：

• 时间复杂度：O(N)，其中 N 为二叉树节点的数目。
• 空间复杂度：O(N)。使用的空间由递归栈的深度决定，它等于当前节点在二叉树中的高度