226 Invert Binary Tree
226. Invert Binary Tree
1. Question
Invert a binary tree.
4
/ \
2 7
/ \ / \
1 3 6 9
to
4
/ \
7 2
/ \ / \
9 6 3 1
2. Implementation
(1) DFS
class Solution {
public TreeNode invertTree(TreeNode root) {
if (root == null) {
return null;
}
TreeNode left = root.left;
TreeNode right = root.right;
root.left = invertTree(right);
root.right = invertTree(left);
return root;
}
}
(2) BFS
class Solution {
public TreeNode invertTree(TreeNode root) {
if (root == null) {
return null;
}
Queue<TreeNode> queue = new LinkedList<>();
queue.add(root);
while (!queue.isEmpty()) {
int size = queue.size();
for (int i = 0; i < size; i++) {
TreeNode curNode = queue.remove();
TreeNode temp = curNode.left;
curNode.left = curNode.right;
curNode.right = temp;
if (curNode.left != null) {
queue.add(curNode.left);
}
if (curNode.right != null) {
queue.add(curNode.right);
}
}
}
return root;
}
}
3. Time & Space Complexity
DFS: 时间复杂度: O(n), 空间复杂度O(n), 平均复杂度是O(logn), 当树是平衡的时候
BFS: 时间复杂度: O(n), 空间复杂度O(w), w为一行中node最多的个数
Last updated
Was this helpful?