[数据结构与算法]Leetcode NO.226 Invert Binary Tree 翻转二叉树

1.问题描述

翻转一棵二叉树。

2.测试用例

示例 1

输入：

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

输出：

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

3.代码

节点信息

public class TreeNode {
    public int val;
    public TreeNode left;
    public TreeNode right;


    public TreeNode(int val) {
        this.val = val;
    }

    public TreeNode(int val, TreeNode left, TreeNode right) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}

1.前序反转

code

public TreeNode invertTreeWithPreOrder(TreeNode root) {
    if (root == null) {
        return null;
    }
    TreeNode tmp = root.left;
    root.left = root.right;
    root.right = tmp;
    invertTreeWithPreOrder(root.left);
    invertTreeWithPreOrder(root.right);
    return root;
}

复杂度

* 时间复杂度 O（n）
* 空间复杂度 O(logn)

2.后序反转

code

public TreeNode invertTreeWithPostOrder(TreeNode root) {
    if (root == null) {
        return null;
    }
    invertTreeWithPostOrder(root.left);
    invertTreeWithPostOrder(root.right);
    TreeNode tmp = root.left;
    root.left = root.right;
    root.right = tmp;
    return root;
}

复杂度

* 时间复杂度 O（n）
* 空间复杂度 0 (logn)