文章目录
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)