leetcode1104二叉树寻路

迷南。 2022-09-02 03:52 37阅读 0赞

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTY3MjQwNA_size_16_color_FFFFFF_t_70]  
`1. 若已知一节点为 i，则该节点的左孩子节点为 (2 * i)，右孩子节点为 (2 * i + 1)且该节点的父节点为 (i / 2)`  
`2. 二叉树中第i层一共2^(i-1)个数，前i-1层一共2^(i-1)-1个数，前i层一共2^i-1`  
`3. 1+....+2^n = a1*(1-q^n)/(1-q)`

1.  该种二叉树的路径求法:

while (label)
     { 
         ans[i--] = label;
         label = label>>1;
     }

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTY3MjQwNA_size_16_color_FFFFFF_t_70 1]

`第i层的第一个数为 l = 2^(i-1)，最后一个为 r = 2^i-1，值都中心对称，当反转的时候，13 = r - l +10`  
**注意**  
``1. 总层数为偶数时要反转奇数层，总层数为奇数时要反转偶数层`，画图就能了解到为什么了``

代码

#include<stdio.h>
    #include<math.h>
    #include<ctype.h>
    #include<stdlib.h>
    /** * Note: The returned array must be malloced, assume caller calls free(). */
    int* pathInZigZagTree(int label, int* returnSize){ 
        int cen=1,i=0;
        while (1)
        { 
            if((1<<cen)>label&&(1<<(cen-1))<=label)
                break;
            else cen++;
        }
        printf("cen = %d\n",cen);
        int *ans = (int*)malloc(sizeof(int)*cen);
        i = cen-1;
        while (label)
        { 
            ans[i--] = label;
            label = label>>1;
        }
        int j;
        i = 0; 
        for(i=1;i<cen;i++)
        { 
            j = i+1;
            printf("%d ",ans[i]);
            if(j%2==0&&cen%2==1){ 
                int l = 1<<(j-1);
                int r = (1<<j)-1;
                ans[i] = r - ans[i] +l;
            }
            else if(j%2==1&&cen%2==0){ 
                int l = 1<<(j-1);//注意是1不是2
                int r = (1<<j)-1;
                ans[i] = r - ans[i] +l;
            }
    
            
        }
        printf("\n");
        *returnSize = cen;
        return ans;
    }
    
    int main(){ 
        int label = 26;
        int returnsize = 0;
        int *ans = pathInZigZagTree(label,&returnsize);
        int i;
        printf("last:\n");
        for(i=0;i<returnsize;i++)
            printf("%d ",ans[i]);
        printf("\n");
        free(ans);
    }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTY3MjQwNA_size_16_color_FFFFFF_t_70]: /images/20220829/416691f2ae484cf5b3768f10ea7b1951.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTY3MjQwNA_size_16_color_FFFFFF_t_70 1]: /images/20220829/ae64b6fbafad4152af8d7f6926287a23.png