|
| 1 | +packageeasy; |
| 2 | + |
| 3 | +importjava.util.LinkedList; |
| 4 | +importjava.util.Queue; |
| 5 | + |
| 6 | +importclasses.TreeNode; |
| 7 | + |
| 8 | +/**226. Invert Binary Tree |
| 9 | +
|
| 10 | + Total Accepted: 111483 |
| 11 | + Total Submissions: 234377 |
| 12 | + Difficulty: Easy |
| 13 | +
|
| 14 | +Invert a binary tree. |
| 15 | +
|
| 16 | + 4 |
| 17 | + / \ |
| 18 | + 2 7 |
| 19 | + / \ / \ |
| 20 | +1 3 6 9 |
| 21 | +
|
| 22 | +to |
| 23 | +
|
| 24 | + 4 |
| 25 | + / \ |
| 26 | + 7 2 |
| 27 | + / \ / \ |
| 28 | +9 6 3 1 |
| 29 | +
|
| 30 | +Trivia: |
| 31 | +This problem was inspired by this original tweet by Max Howell: |
| 32 | +
|
| 33 | + 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.*/ |
| 34 | +publicclassInvertBinaryTree { |
| 35 | +//then I turned to Editorial solution, it provides an iterative version: time complexity is the same with recursion version: O(n), space complexity could be O(n) which is worse than |
| 36 | +//the recursive version which is O(h), h is the height of the tree since recursion might place h recursive calls on the stack |
| 37 | +publicTreeNodeinvertTree_Editorial_solution_iterative(TreeNoderoot){ |
| 38 | +if(root ==null)returnroot; |
| 39 | +//basically using the idea of BFS |
| 40 | +Queue<TreeNode>q =newLinkedList<TreeNode>(); |
| 41 | +q.offer(root); |
| 42 | +while(!q.isEmpty()){ |
| 43 | +TreeNodecurr =q.poll(); |
| 44 | +TreeNodetemp =curr.left; |
| 45 | +curr.left =curr.right; |
| 46 | +curr.right =temp; |
| 47 | +if(curr.left !=null)q.offer(curr.left); |
| 48 | +if(curr.right !=null)q.offer(curr.right); |
| 49 | +} |
| 50 | +returnroot; |
| 51 | +} |
| 52 | + |
| 53 | +//a super classic recursion problem, I'm really glad that I made this one AC'ed now the first time I submitted it. Practice does make perfect! |
| 54 | +publicTreeNodeinvertTree(TreeNoderoot) { |
| 55 | +if(root ==null)returnroot; |
| 56 | +TreeNodetemp =root.left; |
| 57 | +root.left =root.right; |
| 58 | +root.right =temp; |
| 59 | +invertTree(root.left); |
| 60 | +invertTree(root.right); |
| 61 | +returnroot; |
| 62 | +} |
| 63 | +} |