leetcode#1104 二叉树寻路

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

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

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

示例：

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

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

提示：

1 <= label <= 10^6
来源：力扣（LeetCode）
链接:https://leetcode-cn.com/problems/path-in-zigzag-labelled-binary-tree

题解性能：

思路：

看到题目的一刻，想到建立完全树，只不过这个建树的顺序比较奇特。

1）种树（未用）

起初中规中矩，希望可以通过建两颗树来解决问题，于是想到两种种树的方法：

第一种： 生成的时候，赋值按照规矩来，也就是按照数字顺序建类似一条链表的线性结构，然后利用数学规律找到某个endNum 数字的父节点-》直至root

第二种： 直接前序建完全树，直到节点数目达到endNum停止（最终因为难以使父亲不同的节点横线连接未采用）

但还是写了前序建立完全树代码：

int locCol(int label)  //按照完全树的定位某个在第几行
{
   
    int cols=1;
    int sum=1;
    int base=2;
    while(sum < label)
    {
   
        cols ++;
        sum += base;
        base *= 2;
    }

    return cols;
}

void preOrderCreate(treeNode &tr,int endNum) //按照顺序前向建树
{
   
    data ++;
    if(data == endNum)
    {
   
        cout<<"end"<<endl;
        tr = new Node;
        tr->val = data;
        tr->left=NULL;
        tr->right=NULL;
        tr->next=NULL;
        return; //终点限制
    }
    else if(depth == locCol(endNum))
    {
   
        cout<<"end col"<<endl;
        tr = new Node;
        tr->val = data;
        tr->left=NULL;
        tr->right=NULL;
        return;  //层数限制
    }
    else
    {
   

        tr = new Node;
        tr->val = data;

        depth++;
        preOrderCreate(tr->left,endNum);
 
        if(data == endNum) return;
 
        preOrderCreate(tr->right,endNum);
        depth--;
        //回到父节点，此时的data是父节点的data
        if(tr->left!=NULL && tr->right!=NULL)
        {
   
            if(locCol(data)%2==0)  //所以儿子们在奇数行
            {
   
                tr->left->next = tr->right;
            }
            else //所以儿子们在偶数行
            {
   
                tr->right->next = tr->left;
            }
        }
    }
}

（2种建树示意图）

2）找规律用数学方法

舍弃建树，尝试找规律，最后研究出一个神奇的公式：
$f a t h e r = (s o n / 2) + (a r e a [t e m p C o l - 1] - 2 * r o u n d (f l o a t (s o n - p r e A r e a [t e m p C o l - 1]) / 2) + 1)$
其中，tempCol 是当前子节点 son 所在的行（行标从1开始）

area 数组存储每个行有多少个节点，故 area[tempCol-1] 代表当前子节点前一行有多少个节点

preAre 数组存储前x行一共多少个节点，故 preArea[tempCol-1] 代表当前子节点之前的所有行节点数之和

（不同符号含义示意图）

怎么得出这个公式的呢？~~只能说是小学计算 + 灵感~~

是完全树的性质给的灵感，对于一颗数字顺序存储的完全二叉树，父子编号有这样的性质：

父节点 = 子节点 / 2（int型除法，直接保留整数部分）

因此，从这个入手，加上本题中每行奇怪的顺序，加上一个偏移量就可以从子得到父，然后经一番推导就得到以上公式。

想通了这一点，树不用建了，甚至一个顺序存储的数组也不用建了——上代码（主要关注函数pathInZigZagTree）：

题解代码：

class Solution {
   
public:
    int locCol(int label)  //按照完全树的定位某个在第几行
    {
   
    int cols=1;
    int sum=1;
    int base=2;
    while(sum < label)
    {
   
        cols ++;
        sum += base;
        base *= 2;
    }

    return cols;
    }

    vector<int> pathInZigZagTree(int endNum) {
   
    int sum=1;
    int base=1;
    int col=1;
    int cols=locCol(endNum);
    int *area = new int[cols+2]; //每个段的树的量
    int *pre_area = new int[cols+1];  //前面的每一段的总数
    int footprint = endNum;
    vector<int> path;
    area[0] = -1;
    pre_area[0] = -1;

    while(col <= cols)
    {
   
        area[col] = base; //每一段的树
        pre_area[col] = sum; //前col段的总数
        col ++;
        base *= 2;
        sum += base;
    }



    for(int i=1;i<=cols;i++)
    {
   
        path.insert(path.begin(),footprint);
        int temp_col = locCol(footprint); //当前行
        int pre = pre_area[temp_col-1]; //之前和
        int temp = area[temp_col];  //当前行数目
        int cal = (footprint / 2) + (area[temp_col-1] - 2 * round(float(footprint - pre)/2) + 1);  //呕心力学
        footprint = cal;

    }

    return path;
    }
};

int stringToInteger(string input) {
   
    return stoi(input);
}

string integerVectorToString(vector<int> list, int length = -1) {
   
    if (length == -1) {
   
        length = list.size();
    }

    if (length == 0) {
   
        return "[]";
    }

    string result;
    for(int index = 0; index < length; index++) {
   
        int number = list[index];
        result += to_string(number) + ", ";
    }
    return "[" + result.substr(0, result.length() - 2) + "]";
}

int main() {
   
    string line;
    while (getline(cin, line)) {
   
        int label = stringToInteger(line);
        vector<int> ret = Solution().pathInZigZagTree(label);
        string out = integerVectorToString(ret);
        cout << out << endl;
    }
    return 0;
}