算法题解：二叉树寻路

31/Jul/2021 · 3 minute read

本题来自 Leetcode 的 1104 题，是一道很有趣的考察二叉树数据结构的题，同时由于二叉树父子节点之间的特殊关系，同时还可以运用到位运算来巧妙解题。

先贴一下题目：

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

示例 1：

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

示例 2：

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

算法题解思路1：运用二叉树的节点的数值特性推导出公式求解

观察这个“之”字形二叉树，我们可以得出几个特点：

  1. 假如所有节点都是按照从左到右依次递增，按照二叉树的特性，我们可以归纳总结出：
    记 vi = 某个节点的数值
v(左子节点) = 2 x vi
v(右子节点) = 2 x vi + 1

相反：
v(父节点) = vi / 2
  2. 对于每层(第一层为根节点)的第一个和最后一个节点，会有：
    v（第一个节点）= 2^(n-1)  // 2 的 n-1 次方，n为当前层数
v（最后一个节点）= 2^n - 1 // 2 的 n 次方减 1，n为当前层数
  3. 对于任意一个数值，可以求出其所在的层数为：
    level = log2(N) + 1
  4. 从根节点开始，所有奇数层的节点是从左到右依次递增的；而所有偶数层的节点是从右到左依次递增的；
  5. 对于某一层的所有节点来说，它们都是一个等差数列，所以数列对称位置上的两个节点数值之和总是相等，即第一个节点和最后一个节点的值之和一定等于第二个节点和倒数第二个节点的值之和。结合第 2 点，这个和始终为 2^(n-1) + 2^n - 1。

结合以上5点性质，我们写出求任意一个节点的伪代码为：

def getParentLabel(label: int) -> label: int
    level := log2(label) + 1 // 求 label 所在层级
    如果 level 为偶数：
        则获得当前节点的对称节点的值，再求父节点的值
    如果 level 为奇数：
        则直接求父节点的值，再求父节点的对称节点的值

def pathInZigZagTree(label: int) -> path: []int
    path := [label] // label 是路径的最后一个节点
    loop
        如果 label 等于 1，则跳出循环，因为此时已经到达根节点
        父节点 := getParentLabel(label)
        将父节点加到 path 的开头位置
        label := 父节点
    返回 path

对应的 Golang 代码为：

import "math"

func getParentLabel(label int) int {
    n := int(math.Log2(float64(label))) + 1
    if n % 2 == 0 {
        label = int(math.Pow(2, float64(n-1)) + math.Pow(2, float64(n))) - 1- label // 先对称翻转
        return label / 2 // 再算父节点
    }
    return int(math.Pow(2, float64(n-2)) + math.Pow(2, float64(n-1))) - 1 - label / 2 // 直接算父节点的对称翻转节点
}

func pathInZigZagTree(label int) []int {
    if label == 1 {
        return []int{1}
    }

    original := label
    path := []int{}
    for {
        if label == 1 {
            break
        }

        label = getParentLabel(label)
        path = append(path, label)
    }
    for i := 0; i < len(path) / 2; i++ {
        path[i], path[len(path) - 1 - i] = path[len(path) - 1 - i], path[i]
    }
    path = append(path, original)
    return path
}

提交运行，结果为双 100。

算法题解思路2：位运算

这个思路其实还是基于思路1的归纳总结，但是更巧妙的是可以结合位运算的特性，因为我们都知道，对于对2乘法和对2除法，在位运算里都是简单的位移操作，往左移1位就是乘以2，反之，往右移就是除以2。

那么好，怎样将位运算技巧运用进来？我们重新回顾上面 5 个性质中的部分性质：

  1. 父节点的计算：

    v(父节点) = vi / 2
// 换成位计算，就是：
v(父节点) = vi >> 1 // 即右移1位

  2. 对称节点的和为 2^(n-1) + 2^n - 1，也就是二进制的 0b100...0（n-1个0）加上 0b00...00（n个0）再减去 0b1，即 0b1011...11（n-1个低位均为1）。

  3. 而对于某一层的节点的值，其值的范围为[2^(n-1), 2^n-1]，亦即[0b100...00，0b111...11]，总位数为n，结合上面新的第 2 点，我们可以知道，每个节点，与其对称节点的各自的值的 n-1 个低位相加刚好等于 0b11...11（n-1位的二进制），也就是说，一个节点的对称节点的值，刚好等于这个节点的值的最高1位，加上剩余n-1位的反码。

  4. 分情况讨论：
    4.1. 如果当前行是偶数，则计算父节点值的过程是：

     value = (value & 100...00 + !(val & 11...11))  // 100...00 表示保留高1位，1...11 表示保留低 n - 1 位
 value >> 1

    4.2. 如果当前行是奇数，则计算父节点值的过程是： value » 1 value = (value & 100…00 + !(val & 11…11)) // 100…00 表示保留高1位，1…11 表示保留低 n - 2 位 当 value ≠ 1 时，可以简单右移操作不管放在前面还是后面执行，都不会影响计算结果。

按照新的思路，可以得出以下算法实现：

import "math"

func getParentLabel(label int) int {
    n := int(math.Log2(float64(label)))
    label = label >> 1
    mask := 1 << (n-1) // 0b1000000, n-1个0，用来保留最高位
    lowMask := mask - 1 // 0b0111111, n-1个1，用来取低n-1位
    label = label & mask + (^label & lowMask)
    return label
}

func pathInZigZagTree(label int) []int {
    if label == 1 {
        return []int{1}
    }

    original := label
    path := []int{}
    for {
        if label == 1 {
            break
        }

        label = getParentLabel(label)
        path = append(path, label)
    }
    for i := 0; i < len(path) / 2; i++ {
        path[i], path[len(path) - 1 - i] = path[len(path) - 1 - i], path[i]
    }
    path = append(path, original)
    return path
}

提交后，同样双100通过，对比两种解题思路，基本思路一致，从结果看，执行用时和内存消耗也确实一致，只不过一种是直观表达，一种是位运算角度计算，而后者还统一了计算逻辑。