问题描述
翻转一棵二叉树。
示例:
输入:
输出:
解法一(递归):
翻转二叉树,可以先交换根节点的两个子节点,然后通过同样的方式在交换根节点的子节点的两个子节点……一直这样交换下去,画个图看一下
代码如下:
public TreeNode invertTree(TreeNode root) { if (root == null) { return null; } //交换节点,定义一个临时节点 TreeNode left = root.left; root.left= root.right; root.right=left; //递归调用.左右子树都递归 invertTree(root.right); invertTree(root.left); return root; }
解法二(BFS):
如果对树的遍历比较熟悉的话,我们只要遍历树的所有节点,然后把他们的左右子节点相互交换即可,如果这样写,那么答案就比较多了。这里来看下二叉树的BFS解法,二叉树的BFS就是一层一层的遍历,像下面这样
每次遍历节点的时候都要交换子节点,代码如下:
public TreeNode invertTree1(TreeNode root) { if (root == null) return null; Queue<TreeNode> queue = new LinkedList<>(); queue.add(root); while (!queue.isEmpty()) { TreeNode poll = queue.poll(); //交换节点 TreeNode left = poll.left; poll.left = poll.right; poll.right = left; if (poll.left != null) { queue.add(poll.left); } if (poll.right != null) { queue.add(poll.right); } } return root; }
总结
这道题还可以用stack来解决,只要能遍历二叉树的所有节点都可以轻松完成,通过二叉树的遍历,递归和非递归。