13年10月 月赛第一场 set 1 无限完全二叉树的层次遍历

题目

给定这么一个二叉树, 求解 (1) 对于给定正整数 n, 求解其值, 比如当 n = 5 时, 返回 p = 3, q = 2 (2) 对于给定的 p,q 返回其序号 n

思路

1. 最初以为这是道数学题, 但当画出第四层叶子节点时, 发现即便这是道数学问题, 也可以用递归求解. 同时因为此题属于完全二叉树, 所以使用递归效率也不会太差, 毕竟每次递归数据规模都可以减少一半

2. 已知 n 或已知 p,q 都属于某一个叶子节点, 因此我们需要从底向上推导, 属于 bottomUp 算法. 我曾总结过 bottomUp 算法, 那次的结论是使用后序遍历即可, 但这是一道逻辑上的树, 不能进行后续遍历, 所以需要另想方法

3. 对于第一问, 已知 n, 通过手工计算的话, 是根据 n 的奇偶性选择向上走的方向, 一直走到 root, 记录路径再回溯回来. 用递归实现, 有点意思, 这里我还想了蛮长时间, 毕竟第一次接触, 感觉有点绕, 最后写出这样的代码

pair<int, int> bottomUp(int n, int &p, int &q) {
    if(n == 1) {
        p = 1;
        q = 1;
        return pair<int, int>(1,1);
    }
    // n != 1;
    pair<int, int> retVal = bottomUp(n/2, p, q);

    if(n & 1) { // odd number
        p = p+q;
    }else{
        q = p+q;
    }
}

代码的精髓在于使用一个函数来做出了 bottomUp and 回溯回去两个过程

4. 第 2 问就显得更加直接了, 思路相同

void nth(int p, int q, int &n) {
    if(p == 1 && q == 1) {
        n = 1;
        return;
    }
    if(p > q) {
        int newp = p-q;
        nth(newp, q, n);
        n = n*2 +1;
    }else{
        int newq = q-p;
        nth(p, newq, n);
        n *= 2;
    }
}

想到 Leetcode 上一道题, 求解十进制数中 1 的个数, 递归求法同样奇妙

13年10月 月赛第一场 set 1 无限完全二叉树的层次遍历,布布扣,bubuko.com

13年10月 月赛第一场 set 1 无限完全二叉树的层次遍历

原文：http://www.cnblogs.com/xinsheng/p/3575676.html