226. Invert Binary Tree

  • 51.8%

https://leetcode.com/problems/invert-binary-tree/#/description

1
2
3
4
5
6
7
8
9
10
11
12
13
Invert a binary tree.

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

Trivia:

This problem was inspired by this original tweet by Max Howell:

Google: 90% of our engineers use the software you wrote (Homebrew), but you can’t invert a binary tree on a whiteboard so fuck off.


对应剑指offer 19题

三种方法:递归、DFS、BFS

方法一:递归

1
2
3
4
5
6
7
8
9
10
11
12
13
14
public class Solution {
public TreeNode invertTree(TreeNode root) {

if (root == null) {
return null;
}

final TreeNode left = root.left,
right = root.right;
root.left = invertTree(right);
root.right = invertTree(left);
return root;
}
}

我的实现:

1
2
3
4
5
6
7
8
9
10
11
class Solution {
public:
TreeNode* invertTree(TreeNode* root) {
if(root==NULL) return root;
TreeNode* left = invertTree(root->left);
TreeNode* right = invertTree(root->right);
root->left = right;
root->right = left;
return root;
}
};

我的代码实现:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
TreeNode* invertTree(TreeNode* root) {
if(!root) return root;
TreeNode* left = invertTree(root->left);
TreeNode* right = invertTree(root->right);
root->right = left;
root->left = right;
return root;
}
};

方法二:DFS,使用栈作为辅助,使用栈的方法是把root压入栈,栈不为空时,弹出当前栈顶,针对栈顶的左右节点进行反转,若左非空,左压入,右非空,右压入

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
public class Solution {
public TreeNode invertTree(TreeNode root) {

if (root == null) {
return null;
}

final Deque<TreeNode> stack = new LinkedList<>();
stack.push(root);

while(!stack.isEmpty()) {
final TreeNode node = stack.pop();
final TreeNode left = node.left;
node.left = node.right;
node.right = left;

if(node.left != null) {
stack.push(node.left);
}
if(node.right != null) {
stack.push(node.right);
}
}
return root;
}
}

方法三:

BFS,层序遍历的方法,注意,要把层序当做先序,中序,后续遍历一样普通和容易想到的方法。

层序遍历,具体cpp实现,还需要再思考。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
public class Solution {
public TreeNode invertTree(TreeNode root) {

if (root == null) {
return null;
}

final Queue<TreeNode> queue = new LinkedList<>();
queue.offer(root);

while(!queue.isEmpty()) {
final TreeNode node = queue.poll();
final TreeNode left = node.left;
node.left = node.right;
node.right = left;

if(node.left != null) {
queue.offer(node.left);
}
if(node.right != null) {
queue.offer(node.right);
}
}
return root;
}
}

https://discuss.leetcode.com/topic/16138/recursive-and-non-recursive-c-both-4ms/3

Recursive and non-recursive C++ both 4ms

Recursive

1
2
3
4
5
6
7
8
TreeNode* invertTree(TreeNode* root) {
if (root) {
invertTree(root->left);
invertTree(root->right);
std::swap(root->left, root->right);
}
return root;
}

Non-Recursive

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
TreeNode* invertTree(TreeNode* root) {
std::stack<TreeNode*> stk;
stk.push(root);

while (!stk.empty()) {
TreeNode* p = stk.top();
stk.pop();
if (p) {
stk.push(p->left);
stk.push(p->right);
std::swap(p->left, p->right);
}
}
return root;
}

https://discuss.leetcode.com/topic/16062/3-4-lines-python/4

3-4 lines Python

1
2
3
4
def invertTree(self, root):
if root:
root.left, root.right = self.invertTree(root.right), self.invertTree(root.left)
return root

Maybe make it four lines for better readability:

1
2
3
4
5
def invertTree(self, root):
if root:
invert = self.invertTree
root.left, root.right = invert(root.right), invert(root.left)
return root

And an iterative version using my own stack:

1
2
3
4
5
6
7
8
def invertTree(self, root):
stack = [root]
while stack:
node = stack.pop()
if node:
node.left, node.right = node.right, node.left
stack += node.left, node.right
return root

https://discuss.leetcode.com/topic/21271/python-solutions-recursively-dfs-bfs

Python solutions (recursively, dfs, bfs).

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
# recursively
def invertTree1(self, root):
if root:
root.left, root.right = self.invertTree(root.right), self.invertTree(root.left)
return root

# BFS
def invertTree2(self, root):
queue = collections.deque([(root)])
while queue:
node = queue.popleft()
if node:
node.left, node.right = node.right, node.left
queue.append(node.left)
queue.append(node.right)
return root

# DFS
def invertTree(self, root):
stack = [root]
while stack:
node = stack.pop()
if node:
node.left, node.right = node.right, node.left
stack.extend([node.right, node.left])
return root

https://discuss.leetcode.com/topic/16039/straightforward-dfs-recursive-iterative-bfs-solutions/3

Straightforward DFS recursive, iterative, BFS solutions

As in many other cases this problem has more than one possible solutions:

Lets start with straightforward - recursive DFS - it’s easy to write and pretty much concise.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
public class Solution {
public TreeNode invertTree(TreeNode root) {

if (root == null) {
return null;
}

final TreeNode left = root.left,
right = root.right;
root.left = invertTree(right);
root.right = invertTree(left);
return root;
}
}

The above solution is correct, but it is also bound to the application stack, which means that it’s no so much scalable - (you can find the problem size that will overflow the stack and crash your application), so more robust solution would be to use stack data structure.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
public class Solution {
public TreeNode invertTree(TreeNode root) {

if (root == null) {
return null;
}

final Deque<TreeNode> stack = new LinkedList<>();
stack.push(root);

while(!stack.isEmpty()) {
final TreeNode node = stack.pop();
final TreeNode left = node.left;
node.left = node.right;
node.right = left;

if(node.left != null) {
stack.push(node.left);
}
if(node.right != null) {
stack.push(node.right);
}
}
return root;
}
}

Finally we can easly convert the above solution to BFS - or so called level order traversal.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
public class Solution {
public TreeNode invertTree(TreeNode root) {

if (root == null) {
return null;
}

final Queue<TreeNode> queue = new LinkedList<>();
queue.offer(root);

while(!queue.isEmpty()) {
final TreeNode node = queue.poll();
final TreeNode left = node.left;
node.left = node.right;
node.right = left;

if(node.left != null) {
queue.offer(node.left);
}
if(node.right != null) {
queue.offer(node.right);
}
}
return root;
}
}

If I can write this code, does it mean I can get job at Google? ;)

谢谢你,可爱的朋友。