Invert a binary tree.
4 / \ 2 7 / \ / \ 1 3 6 9to
4 / \ 7 2 / \ / \ 9 6 3 1Trivia:
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.Understand the problem:
The problem is very easy to understand. Just to re-link root's left child to the right sub-tree, and root's right child to the left sub-tree. Only one thing to note is we must use a temp Node when we do the swap.
Code (Java):
/** * 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 null; } TreeNode temp = root.left; root.left = invertTree(root.right); root.right = invertTree(temp); return root; } }
A BFS Solution:
/** * 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) { Queue<TreeNode> queue = new LinkedList<TreeNode>(); if (root == null) { return null; } queue.offer(root); while (!queue.isEmpty()) { TreeNode curr = queue.poll(); if (curr.left != null) { queue.offer(curr.left); } if (curr.right != null) { queue.offer(curr.right); } TreeNode temp = curr.left; curr.left = curr.right; curr.right = temp; } return root; } }
No comments:
Post a Comment