[数据结构与算法]1104. 二叉树寻路(java)

题目

在一棵无限的二叉树上，每个节点都有两个子节点，树中的节点 逐行 依次按 “之” 字形进行标记。如下图所示，在奇数行（即，第一行、第三行、第五行……）中，按从左到右的顺序进行标记；而偶数行（即，第二行、第四行、第六行……）中，按从右到左的顺序进行标记

思路

看上去感觉是数学题直接找公式，贴一下题解：https://leetcode-cn.com/problems/path-in-zigzag-labelled-binary-tree/solution/er-cha-shu-xun-lu-by-leetcode-solution-ryx0/

奇数行按从左到右顺序排列，而偶数行按从右到左顺序排列，可以考虑将偶数行转换成按从左到右的顺序进行排列，
当 i是偶数时，如果第i行的一个节点的「从左到右标号」为label，则该节点的实际标号为:

流程：

1. 判断当前label位于第几行
2. 若为偶数行将其转为从左到右标号顺序
3. 通过while循环将每个父节点存入list中，偶数行需要将从左到右标号改为从右到左标号
4. 逆转list，返回list

代码

class Solution {
    public List<Integer> pathInZigZagTree(int label) {
        int row = 1, rowStart = 1;
        while(rowStart * 2 <= label){
            row++;
            rowStart*=2;
        }
        // 偶数行
        if(row % 2 == 0){
            // 获取从左到右标号
            label = getReverse(label, row);
        }
        List<Integer> path = new ArrayList<Integer>();
        while(row > 0){
            if(row % 2 == 0){
                path.add(getReverse(label,row));
            } else {
                path.add(label);
            }
            row--;
            label >>= 1;
        }
        Collections.reverse(path);
        return path;
    }
    
    public int getReverse(int label, int row){
        return (1 << row - 1) + (1 << row) - 1 - label;
    }
}