C/C++教程

leetCode987 二叉树的垂序遍历(hard)

本文主要是介绍leetCode987 二叉树的垂序遍历(hard),对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

好久没更新了,因为刚换了工作,比较忙。这次更新就由这道表面hard,实则medium的题目开始吧,同时希望自己的生活工作哪怕遇到hard,但也能积极面对,最后发现其实也就那回事!

审题:

给你二叉树的根结点 root ,请你设计算法计算二叉树的 垂序遍历 序列。

对位于 (row, col) 的每个结点而言,其左右子结点分别位于 (row + 1, col - 1) 和 (row + 1, col + 1) 。树的根结点位于 (0, 0) 。

二叉树的 垂序遍历 从最左边的列开始直到最右边的列结束,按列索引每一列上的所有结点,形成一个按出现位置从上到下排序的有序列表。如果同行同列上有多个结点,则按结点的值从小到大进行排序。

返回二叉树的 垂序遍历 序列。

来源:力扣(LeetCode)
读完题目,应该还是很明白的,就是从左到右,从上到下,相同位置则从小到大,来对二叉树进行遍历

 

思考:

我们可以记录每个节点的位置信息,比如可以定义一个int[] a, a[0]记录x轴坐标,a[1]记录y轴坐标,a[2]记录节点的值,然后用一个list去储存这个a,最后对list按照上面的要求来进行排序即可,详细见代码和注释:

        public List<List<Integer>> verticalTraversal(TreeNode root) {
            List<int[]> list = new ArrayList<>();
            listNode(root, list, null, true);
            // 从左到右,从上到下,相同位置则从小到大进行排序
            list.sort((o1, o2) -> {
                if (o1[0] != o2[0]) {
                    return o1[0] - o2[0];
                } else if (o1[1] != o2[1]) {
                    return o1[1] - o2[1];
                } else return o1[2] - o2[2];
            });

            List<List<Integer>> re = new ArrayList<>();
            List<Integer> ll = new ArrayList<>();
            // 进行分组,同一个x坐标则在一个组
            for (int i = 0; i < list.size() - 1; i++) {
                ll.add(list.get(i)[2]);
                if (list.get(i)[0] != list.get(i + 1)[0]) {
                    re.add(ll);
                    ll = new ArrayList<>();
                }
            }
            // 处理一下最右边的一个节点
            ll.add(list.get(list.size() - 1)[2]);
            re.add(ll);
            return re;
        }


        /**
         * 进行递归先序遍历,为了通过父节点信息对子节点位置进行计算
         * 定义一个int[3] 分别存x y val
         *
         * @param fa 父亲节点的位置信息
         * @param b  左节点true 右节点false
         */
        void listNode(TreeNode node, List<int[]> list, int[] fa, boolean b) {
            if (node == null) return;
            int[] a = new int[3];
            // fa为null 的时候说明是父亲节点,那么x=0,y=0,默认值
            if (fa != null) {
                if (b) {
                    // 左节点x向左进行偏移一位
                    a[0] = fa[0] - 1;
                } else {
                    // 右节点x向右进行偏移一位
                    a[0] = fa[0] + 1;
                }
                // 无论左右节点,y都要+1
                a[1] = fa[1] + 1;
            }
            //保存节点值
            a[2] = node.val;
            list.add(a);
            listNode(node.left, list, a, true);
            listNode(node.right, list, a, false);
        }

总结:

这道题思路还是很清晰的,一定要熟练掌握二叉树的遍历,尤其是进行遍历的时候,保存一些状态值。

这篇关于leetCode987 二叉树的垂序遍历(hard)的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!