LEETCODE 1104. Path In Zigzag Labelled Binary Tree 解题思路分析

题目大意:

在一棵无限的二叉树上,每个节点都有两个子节点,树中的节点 逐行 依次按 “之” 字形进行标记。

如下图所示,在奇数行(即,第一行、第三行、第五行……)中,按从左到右的顺序进行标记;

而偶数行(即,第二行、第四行、第六行……)中,按从右到左的顺序进行标记。

给你树上某一个节点的标号 label,请你返回从根节点到该标号为 label 节点的路径,该路径是由途经的节点标号所组成的。

示例 1:

输入:label = 14
输出:[1,3,4,14]
示例 2:

输入:label = 26
输出:[1,2,6,10,26]
 

提示:

1 <= label <= 10^6


如果想查看本题目是哪家公司的面试题,请参考以下免费链接: https://leetcode.jp/problemdetail.php?id=1104

解题思路分析:

题目要求节点元素的排列顺序为蛇形排列。我们可以先将问题简化,假设二叉树所有层的节点都是按照从左向右的顺序排放,问题就会变得容易许多。试想,当一个二叉树每一层都是按照从左到右的顺序依次递增一个数字,那么这个二叉树会存在以下特征:

  1. 每一行的元素个数会存在2的n-1次方个。(第一层1个元素,第二层2个,第三册4个,第4层8个。。。。)
  2. 每一行的第一个元素一定是2的n-1次方这个数字。(第一层首元素是1,第二层是2,第3层是4,第四层是8。。。)也就是说,每一层首元素的值要等于该层元素的个数。
  3. 对于每个元素,它的父节点一定是当前节点值除以2。反过来说,每个元素的两个子节点分别是当前元素值乘以2和当前元素值乘以2再加1。(5的子元素分别是10和11,10和11的母元素都是5)

有了以上的特征,通过给定的数字我们可以轻松的找到其母元素(除以2),一直能找到二叉树的根(元素1)。

这时再考虑二叉树在蛇形排列的情况下如何找到母节点。虽然题目说的是奇数行正序,偶数行倒序的方式排列,但是反过来,奇数行倒序偶数行正序的方式并不会影响最终的结果。简单来说,只要保证相邻行的排序方式是相反的即可。

这样问题就转化为:当已知某一行的某个节点,如何找到该行内对应该节点的对称节点问题。我们举例来说明,比如当前行为4,当前元素为9,那么当前行的总节点数应该为8(2的4-1次方),同时该行的首元素也是8。所以元素9在正序时的index应该为1(9-8=1。注意下标从0开始,1对应的是正数第2个),肉眼可看出相对称倒序倒序坐标应该是6(倒数第二个)。也就是当前层最大index(7)减去正序index(1)的值。因此,正序第6个元素应该是首元素加上6。

最后看下完整代码:

public List<Integer> pathInZigZagTree(int label) {
    int current = label;
    int row = 0;
    // 先求出label所在的行数。
    while(current > 0){
        current /= 2;
        row++;
    }
    List<Integer> res = new ArrayList<>(); // 返回结果
    current = label;
    boolean isReverse=false; // 定义当前行是否需要反转
    while(current >= 1){
        if(isReverse){ // 如果需要反转
            int count = (int)Math.pow(2, row-1); // 计算当前行元素个数
            int reverseIndex = (count - 1) - (current - count); // 计算
            res.add(0, count + reverseIndex); // 将对称值加到结果集中
        }else{
            res.add(0, current); // 如果不需要反转,直接将当前值加入到结果集
        }
        current /= 2; // 找到母节点
        row--; // 行数减
        isReverse = !isReverse; // 更新反转flag
    }
    return res;
}

本题解法用时0ms。

本网站文章均为原创内容,并可随意转载,但请标明本文链接
如有任何疑问可在文章底部留言。为了防止恶意评论,本博客现已开启留言审核功能。但是博主会在后台第一时间看到您的留言,并会在第一时间对您的留言进行回复!欢迎交流!
本文链接: http://leetcode.jp/leetcode-1104-path-in-zigzag-labelled-binary-tree-解题思路分析/
此条目发表在leetcode分类目录,贴了, , 标签。将固定链接加入收藏夹。

发表评论

您的电子邮箱地址不会被公开。