翻转二叉树

问题描述

翻转一棵二叉树。

示例:

输入:

翻转二叉树

 输出:

翻转二叉树

 解法一(递归):

翻转二叉树,可以先交换根节点的两个子节点,然后通过同样的方式在交换根节点的子节点的两个子节点……一直这样交换下去,画个图看一下

翻转二叉树

代码如下:

 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来解决,只要能遍历二叉树的所有节点都可以轻松完成,通过二叉树的遍历,递归和非递归。

上一篇:HDU 2063 过山车 二分匹配


下一篇:HDU 2063 过山车(二分匹配入门)