My simple recursion java solution


  • 29
    S
    public class Solution {
        public TreeNode invertTree(TreeNode root) {
            if(root == null) return null;
            TreeNode tmp = root.left;
            root.left = invertTree(root.right);
            root.right = invertTree(tmp);
            return root;
        }
    }

  • 3
    N

    Nice. This is so trivial, I can't believe that Max Howell guy lost his shit for being asked this in a Google interview.


  • 1
    S

    lol, it perhaps that the interviewers had a strong accent and he failed to figure out the problem.


  • 0
    L

    What are the time and space of big O?


  • 0
    Y

    Both O(N), I think, since we have to check N nodes and have to create N references 'tmp'.


  • 0
    H

    Nice resolution, I think most problems of Binary Tree can be solved by recursion


  • 1
    public TreeNode invertTree(TreeNode root) {
      if (root == null) return null;
      else {
        TreeNode left = root.left;
        root.left = invertTree(root.right);
        root.right = invertTree(left);
        return root;
      }
    }
    

  • 1
    D

    @paplorinc Nice solution :) I must admit that my first intent was to create a copy instead of doing an in-place change. I also thought about an in-place change but decided to do the copy:

    public TreeNode invertTree(TreeNode root) {
        if (root == null) {
            return null;
        } else {
            TreeNode node = new TreeNode(root.val);
            node.left = invertTree(root.right);
            node.right = invertTree(root.left);
            return node;
        }
    }
    

  • 1
    T

    Make it easy to understand

        public TreeNode invertTree(TreeNode root) {
            if(null == root){
                return null;
            }
            
            TreeNode left = invertTree(root.left);
            TreeNode right = invertTree(root.right);
            root.left = right;
            root.right = left;
            
            return root;
        }
    

  • 0
    P

    exactly same, not one character different.


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.