Invert a binary tree.
4 / \ 2 7 / \ / \ 1 3 6 9 to 4 / \ 7 2 / \ / \ 9 6 3 1 我想法就是用递归，然后引用交换每个结点的左右子树。 public class Invert_Binary_Tree_226 { public TreeNode invertTree(TreeNode root) { if(root==null){ return root; } invert(root); return root; } public void invert(TreeNode node){ if(node.left==null&&node.right==null){//两子树都为空 return; } else if(node.left!=null&&node.right!=null){//左右子树都不为空 TreeNode temp=node.left; node.left=node.right; node.right=temp; invert(node.left); invert(node.right); } else if(node.left!=null){//左子树不空，右子树为空 node.right=node.left; node.left=null; invert(node.right); } else{//左子树为空，右子树不空 node.left=node.right; node.right=null; invert(node.left); } } public static void main(String[] args) { // TODO Auto-generated method stub TreeNode root=new TreeNode(4); root.left=new TreeNode(2); root.right=new TreeNode(7); root.left.left=new TreeNode(1); root.left.right=new TreeNode(3); root.right.left=new TreeNode(6); root.right.right=new TreeNode(9); Invert_Binary_Tree_226 i=new Invert_Binary_Tree_226(); i.invertTree(root); System.out.println("1"); } }当然有大神写的比我更简洁，我是没有把所有情况直接统一成一种写法，他做到了。 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; } }但是有大神想到：虽然这个正确，但是很大程度上取决于应用的栈大小，因为这种方法不可伸缩，很有可能溢出栈，所以更加鲁棒性的解决方法是使用队列那样的数据结构，用BFS一层层的遍历。确保把每个元素的左右子树都颠倒一下。 public class Solution { public TreeNode invertTree(TreeNode root) { if (root == null) { return null; } Queue<TreeNode> queue = new LinkedList<>(); queue.offer(root); while(!queue.isEmpty()) { TreeNode node = queue.poll(); TreeNode temp = node.left; node.left = node.right; node.right = temp; if(node.left != null) { queue.offer(node.left); } if(node.right != null) { queue.offer(node.right); } } return root; } }