[leetcode]Invert Binary Tree

[leetcode]Invert Binary Tree | 普通一码农
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.

X. Recursive

1. public void invertTreeSingle(TreeNode cur){
2. if(cur == null) return;
3. TreeNode temp = cur.left;
4. cur.left = cur.right;
5. cur.right = temp;
6. invertTreeSingle(cur.left);
7. invertTreeSingle(cur.right);
8. }
10. public TreeNode invertTree(TreeNode root) {
11. invertTreeSingle(root);
12. return root;
13. }

http://shibaili.blogspot.com/2015/06/day-112-count-complete-tree-nodes.html

    TreeNode* invertTree(TreeNode* root) {

        if (root == NULL) return NULL;

        TreeNode *temp = root->left;

        root->left = invertTree(root->right);

        root->right = invertTree(temp);

         

        return root;

    }

http://www.programcreek.com/2014/06/leetcode-invert-binary-tree-java/
It's better to do null or valid check at first.

public TreeNode invertTree(TreeNode root) { if(root!=null){ helper(root); }   return root; }   public void helper(TreeNode p){   TreeNode temp = p.left; p.left = p.right; p.right = temp;   if(p.left!=null) helper(p.left);   if(p.right!=null) helper(p.right); }

X. Iterative
http://blog.welkinlan.com/2015/09/18/invert-binary-tree-leetcode-lintcode-java/

1. public TreeNode invertTree(TreeNode root) {
2. if(root == null) return root;
3. Queue<TreeNode> queue = new LinkedList<TreeNode>();
4. queue.offer(root);
5. while (!queue.isEmpty()) {
6. TreeNode node = queue.poll();
7. TreeNode nodeLeft = node.left;
8. node.left = node.right;
9. node.right = nodeLeft;
10. if(node.left != null) queue.offer(node.left);
11. if(node.right != null) queue.offer(node.right);
12. }
13. return root;
14. }

X. https://shanzi.gitbooks.io/algorithm-notes/content/problem_solutions/invert_binary_tree.html

    public TreeNode invertTree(TreeNode root) {
        if (root == null) return root;

        Stack<TreeNode> stack = new Stack<TreeNode>();

        TreeNode p = root;
        TreeNode q = null, r = null;
        while (p != null) {
            stack.push(p);
            p = p.left;
        }

        while (!stack.isEmpty()) {
            p = stack.pop();
            q = p.right;
            while (q != null) {
                stack.push(q);
                q = q.left;
            }
            r = p.right;
            p.right = p.left;
            p.left = r;
        }

        return root;
    }

Read full article from [leetcode]Invert Binary Tree | 普通一码农