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.
呵呵
简单的bsf应用，我想我写的比较复杂，但是binary tree level traversal大法好
public class Solution { public TreeNode invertTree(TreeNode root) { if(root==null || (root.left==null&&root.right==null)) return root; LinkedList<TreeNode> q = new LinkedList<TreeNode>(); int curNum =1, nextNum=0; q.add(root); while(!q.isEmpty()){ curNum--; TreeNode n = q.poll(); swapNodes(n); if(n.left!=null){ q.add(n.left); nextNum++; } if(n.right!=null){ q.add(n.right); nextNum++; } if(curNum==0){ curNum = nextNum; nextNum=0; } } return root; } private void swapNodes(TreeNode n ){ if(n==null||(n.left==null&&n.right==null)) return ; TreeNode tmp = n.right; n.right = n.left; n.left = tmp; } }
原文：http://www.cnblogs.com/jiajiaxingxing/p/4572828.html