LeetCode——1104. 二叉树寻路（Java）

题目描述

题干：
在一棵无限的二叉树上，每个节点都有两个子节点，树中的节点 逐行 依次按 “之” 字形进行标记。
如下图所示，在奇数行（即，第一行、第三行、第五行……）中，按从左到右的顺序进行标记；
而偶数行（即，第二行、第四行、第六行……）中，按从右到左的顺序进行标记。  
给你树上某一个节点的标号 label，请你返回从根节点到该标号为 label 节点的路径，
该路径是由途经的节点标号所组成的。

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

示例 2：
输入：label = 26
输出：[1,2,6,10,26]

题解思路

返回之字二叉树中目标节点的路径，我们先假设如果这是正常的二叉树

二叉树中的每个节点的子节点的序号是 label/2 和 label/2 + 1

但是之字二叉树的偶数行会和普通的反转，所以我们先找到偶数行value的公式

因为第i行的总节点个数为 2^（i - 1）个，而前i行的节点个数为 2^i - 1，

所以我们得到偶数行反转后的value的值为 2^(i - 1) + 2^i - 1-label

因此我们可以按照正常的二叉树进行计算，只需要我们遇到偶数行的时候进行转换即可

正确代码

class pathInZigZagTreeSolution {
    public List<Integer> pathInZigZagTree(int label) {
        // 判断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<>();
        while (row > 0) {
            if (row % 2 == 0) {
                path.add(getReverse(label, row));
            } else {
                path.add(label);
            }
            row--;
            label >>= 1;
        }
        Collections.reverse(path);
        return path;
    }

    // 偶数行的value值
    private int getReverse(int label, int row) {
        return (1 << row - 1) + (1 << row) - 1 - label;
    }
}

总结

换位思考，完全二叉树的节点数量规律要牢记，无论是数据结构还是算法都是偏重点

如果文章存在问题或者有更好的题解，欢迎在评论区斧正和评论，各自努力，你我最高处见

LeetCode——1104. 二叉树寻路（Java）

原文：https://www.cnblogs.com/bc-song/p/15073528.html