卖萌的弱渣

I am stupid, I am hungry.

Invert Binary Tree

Invert a binary tree.

Example

1
2
3
4
5

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

to

1
2
3
4
5

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

Solution

(Invert-Binary-Tree.py) download
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution(object):
    def invertTree(self, root):
        """
        :type root: TreeNode
        :rtype: TreeNode
        """

        if root == None:
            return None
        root.left,root.right = root.right,root.left
        if root.left != None:
            self.invertTree(root.left)
        if root.right != None:
            self.invertTree(root.right)
        return root
  • Java solution: recursive. 也可以用stack
(Invert-Binary-Tree.java) download
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    public TreeNode invertTree(TreeNode root) {
        if (root == null)
            return root;
        // swap left,right
        TreeNode tmp = root.left;
        root.left = root.right;
        root.right = tmp;

        invertTree(root.left);
        invertTree(root.right);
        return root;

    }
}