LeetCode刷题-我会翻转二叉树,谷歌还要我吗?

前言说明

算法学习,日常刷题记录。

题目连接

翻转二叉树

题目内容

翻转一棵二叉树。

示例:

输入:

LeetCode刷题-我会翻转二叉树,谷歌还要我吗?_第1张图片

输出:

LeetCode刷题-我会翻转二叉树,谷歌还要我吗?_第2张图片

备注:

这个问题是受到Max Howell的原问题启发的:

谷歌:我们90%的工程师使用您编写的软件(Homebrew),但是您却无法在面试时在白板上写出翻转二叉树这道题,这太糟糕了。

分析过程

翻转二叉树很简单,可以使用递归法。

把二叉树看成是根节点、左孩子、右孩子的整体,整体翻转根节点的左孩子和右孩子。

如果左孩子和右孩子也是树,那么递归下去同样执行相同的方法,直到左孩子和右孩子为空时,递归开始回溯。

最后返回二叉树的根节点,就是翻转后的二叉树。

解答代码

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public TreeNode invertTree(TreeNode root) {
        if (root == null) {
            // 若树节点是空,直接返回空
            return null;
        }

        // 利用递归法,把树看成是根节点、左孩子、右孩子的整体,整体翻转根节点的左孩子和右孩子,如果左孩子和右孩子也是树,那么递归下去同样执行相同的方法,直到左孩子和右孩子为空时,递归开始回溯

        // 获取根节点的左孩子
        TreeNode left = invertTree(root.left);

        // 根节点的左孩子等于右孩子,右孩子等于左孩子,实现翻转
        root.left = invertTree(root.right);
        root.right = left;

        // 返回翻转后的根节点
        return root;
    }
}

提交结果

执行用时0ms,时间击败100.00%的用户,内存消耗35.9MB,空间击败37.33%的用户。

LeetCode刷题-我会翻转二叉树,谷歌还要我吗?_第3张图片

原来翻转二叉树这么简单,我会翻转二叉树,谷歌还要我吗?

延伸分析

但是,我这个人刷题都会把完整的代码写出来,上面的明显不是完整代码,我们在执行运行时,输入的是一个数组,输出的也是一个数组,如图:

LeetCode刷题-我会翻转二叉树,谷歌还要我吗?_第4张图片

而invertTree方法实质输入的是一个二叉树TreeNode对象,所以这里其实存在一个数组转换为二叉树的输入过程,还有一个二叉树转换回数组的输出过程,在LeetCode上刷题时LeetCode后台已经帮你做了转换,但是如果我们要自己写出完整代码,需要自己做转换。

这里只给出一个数组就确定了二叉树,证明是层序遍历,因为前序遍历、中序遍历、后序遍历都无法单独一个数组就推导出二叉树,层序遍历才能单独一个数组推导出二叉树。

层序遍历:逐层从上到下,每层从左到右访问所有节点。

为方便理解,下面举例几个:

输入数组1:[0,null,2,null,4,null,6]

输出二叉树1:

LeetCode刷题-我会翻转二叉树,谷歌还要我吗?_第5张图片

输入数组2:[1,null,2,3]

输出二叉树2:

LeetCode刷题-我会翻转二叉树,谷歌还要我吗?_第6张图片

输入数组3:[0,1,null,null,4]

输出二叉树3:

LeetCode刷题-我会翻转二叉树,谷歌还要我吗?_第7张图片

输入数组4:[4,2,7,1,3,6,9]

输出二叉树4:

LeetCode刷题-我会翻转二叉树,谷歌还要我吗?_第8张图片

数组转为二叉树:有点奇怪的是,我翻了很多算法书本,查阅了很多网上资料,很少看到有提及如何把层序遍历的数组转为二叉树的,下面我整理出了一个转换的方法,请看后面的完整代码arrayToTreeNode方法,通过队列辅助来实现广度优先搜索,即模拟层序遍历时从上到下从左到右的过程,把数组转换为二叉树,要注意考虑数组元素为null的情况,当数组元素为null时,该节点没有孩子,但是自身会占用一个数组元素。

二叉树转为数组:请看后面的完整代码treeNodeToArray方法,也是通过队列辅助来实现广度优先搜索,即模拟层序遍历时从上到下从左到右的过程,先把二叉树转换为两层列表List,两层列表的每一层保存一层树的从左到右的节点值,最后再把两层列表List转换为数组,这里也要注意数组元素为null的情况,若一行元素都为null,那么这一行不要;若一行元素最后一个为null,要去掉最后一个元素。

完整代码如下:

import java.util.*;

public class Main {

    public static void main(String[] args) {
        // 获取输入结果
        Scanner scanner = new Scanner(System.in);
        String str = scanner.next();
        scanner.close();

        // 处理输入结果
        Integer[] nums;
        if ("[]".equals(str)) {
            // 当数组为空
            nums = null;
        } else {
            // 当数组不为空
            String[] strs = str.split("\\[")[1].split("]")[0].split(",");
            int size = strs.length;
            nums = new Integer[size];
            for (int i = 0; i < size; ++i) {
                if ("null".equals(strs[i])) {
                    nums[i] = null;
                } else {
                    nums[i] = Integer.parseInt(strs[i]);
                }
            }
        }

        // 数组转为二叉树
        TreeNode root = arrayToTreeNode(nums);

        // 获取输出结果
        TreeNode result = invertTree(root);
        System.out.println(Arrays.toString(treeNodeToArray(result)));
    }

    // 数组转为二叉树,层序遍历,分层按照从上到下,从左到右的顺序
    private static TreeNode arrayToTreeNode(Integer[] nums) {
        // 利用队列辅助,特别需要注意支持数组元素为null,当数组元素为null时,该节点没有孩子,但是自身会占用一个数组元素
        // 如果该节点的左孩子为null,右孩子不为null,那么数组的下一个元素会从右孩子的子节点开始,因为左孩子为null,没有子节点
        // 例子:[0,null,2,null,4,null,6],[1,null,2,3],[0,1,null,null,4],[4,2,7,1,3,6,9]

        if (nums == null || nums.length == 0) {
            // 若二叉树节点为空,直接返回空
            return null;
        }

        // 数组的开始下标
        int i = 1;

        // 先构造二叉树根节点
        TreeNode root = new TreeNode(nums[0]);

        // 定义当前的二叉树节点,保存临时值
        TreeNode current;

        // 定义当前数组的值
        Integer value;

        // 定义队列,层序遍历创建二叉树
        Queue queue = new LinkedList<>();

        // 先把二叉树根节点放进队列最后
        queue.add(root);

        // 遍历数组,构造二叉树
        while (i < nums.length) {
            // 队列出列第一个元素,获取当前二叉树节点
            current = queue.poll();

            // 获取数组的值,数组下标加1
            value = nums[i++];

            if (value != null) {
                // 创建当前二叉树节点的左孩子
                TreeNode left = new TreeNode(value);

                if (current != null) {
                    // 构造当前二叉树节点的左孩子
                    current.left = left;
                }

                // 把当前二叉树节点的左孩子放进队列最后
                queue.add(left);
            }

            if (i < nums.length) {
                // 获取数组的值,数组下标加1
                value = nums[i++];

                if (value != null) {
                    // 创建当前二叉树节点的右孩子
                    TreeNode right = new TreeNode(value);

                    if (current != null) {
                        // 构造当前二叉树节点的右孩子
                        current.right = right;
                    }

                    // 把当前二叉树节点的右孩子放进队列最后
                    queue.add(right);
                }
            }
        }

        // 返回二叉树的根节点
        return root;
    }

    // 二叉树转为数组,层序遍历,分层按照从上到下,从左到右的顺序,这里因为是翻转二叉树,需要特殊处理,最后一层空的节点也要显示出来,显示为null,这样才能看出翻转后的二叉树的效果
    private static Integer[] treeNodeToArray(TreeNode root) {
        // 定义两层列表,保存整体结果
        List> list = new ArrayList<>();

        if (root == null) {
            // 若二叉树节点为空,直接返回空数组
            return new Integer[0];
        }

        // 通过队列辅助,从上到下完成每层的遍历,在每层遍历时,每遍历完一个节点,就确定这个节点的两个子节点,如果不为空,把子节点放进队列后面,队列保证了树按照层次从上到下遍历,每层从左到右遍历

        // 定义队列
        Queue queue = new LinkedList<>();

        // 先把二叉树的根节点放进队列最后
        queue.add(root);

        // 循环,直到队列的长度为零,结束循环
        while (queue.size() > 0) {
            // 定义内层列表,保存内层结果
            List temp = new ArrayList<>();

            // 获取队列的长度
            int size = queue.size();

            // 遍历队列,每次遍历完成一层树节点的遍历
            for (int i = 0; i < size; ++i) {
                // 队列出列第一个元素
                TreeNode node = queue.poll();

                if (node != null) {
                    // 把出列的元素的值添加到内层列表
                    temp.add(node.val);

                    if (node.left != null) {
                        // 把当前二叉树节点的左孩子放进队列最后
                        queue.add(node.left);
                    } else {
                        // 子节点为空也要放进队列最后,为了适应看出翻转二叉树后的效果
                        queue.add(null);
                    }

                    if (node.right != null) {
                        // 把当前二叉树节点的右孩子放进队列最后
                        queue.add(node.right);
                    } else {
                        // 子节点为空也要放进队列最后,为了适应看出翻转二叉树后的效果
                        queue.add(null);
                    }
                } else {
                    // 把空值添添加到内层列表,为了适应看出翻转二叉树后的效果
                    temp.add(null);
                }
            }

            // 内层列表是否全部元素都是空
            boolean isAllNull = true;

            // 判断内层列表是否全部元素都是空,如果全部元素都是空,那么这一行的内层列表数据是多出的
            for (Integer col : temp) {
                if (col != null) {
                    // 只要有一个元素不是空,那么就不是全部元素都是空
                    isAllNull = false;
                    break;
                }
            }

            if (!isAllNull) {
                // 不是全部元素都是空的内层列表,才添加进两层列表
                list.add(temp);
            }
        }

        // 打印两层列表形式的层序遍历结果
        System.out.println("treeNodeToArray list:" + list);

        // 定义数组的长度
        int count = 0;

        // 遍历两层列表,计算出数组的长度
        for (List row : list) {
            // 每行列表的长度累加
            count += row.size();
        }

        // 定义数组
        Integer[] nums = new Integer[count];

        // 定义数组的下标
        int n = 0;

        // 遍历两层列表,把两层列表转为数组
        for (List row : list) {
            for (Integer col : row) {
                nums[n++] = col;
            }
        }

        if (nums[nums.length - 1] == null) {
            // 若最后一个元素是null,删除最后一个元素,这种情况肯定是null落在右节点上,而且最后的位置,最后一个元素是null不要保留,如果null在左边才是要保留的
            return Arrays.copyOf(nums, nums.length - 1);
        }

        // 返回数组
        return nums;
    }

    // 翻转二叉树
    private static TreeNode invertTree(TreeNode root) {
        if (root == null) {
            // 若树节点是空,直接返回空
            return null;
        }

        // 利用递归法,把树看成是根节点、左孩子、右孩子的整体,整体翻转根节点的左孩子和右孩子,如果左孩子和右孩子也是树,那么递归下去同样执行相同的方法,直到左孩子和右孩子为空时,递归开始回溯

        // 获取根节点的左孩子
        TreeNode left = invertTree(root.left);

        // 根节点的左孩子等于右孩子,右孩子等于左孩子,实现翻转
        root.left = invertTree(root.right);
        root.right = left;

        // 返回翻转后的根节点
        return root;
    }

}

// 定义二叉树
class TreeNode {

    int val;

    TreeNode left;
    TreeNode right;

    TreeNode() {
    }

    TreeNode(int val) {
        this.val = val;
    }

    TreeNode(int val, TreeNode left, TreeNode right) {
        this.val = val;
        this.left = left;
        this.right = right;
    }

}

完整代码获取:https://github.com/zjhpure/al...

原文链接

原文链接:翻转二叉树

你可能感兴趣的