【树】B036_LC_二叉树寻路(找规律)

标签: # 树

一、Problem

在这里插入图片描述

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

1 <= label <= 10^6

二、Solution

方法一:规律

某一个结点 XX 的父节点 fafa 的求法:
fa=left+rightX2fa = left + right - \cfrac{X}{2}
leftrightleft、right 的求法:
left=2d1right=2d1d0 X left = 2^d-1;right = 2^{d-1} (d \geqslant 0,结点\ X\ 深度)
结点 XX 的深度的求法:
d=log2X=logeXloge2d = log_2X = \cfrac{log_eX}{log_e2}

class Solution {
    public List<Integer> pathInZigZagTree(int x) {
        LinkedList<Integer> q = new LinkedList<>();
        q.add(x);
        int d = (int) (Math.log(x) / Math.log(2));

        while (d > 0) {
            x = (int) Math.pow(2, d)-1 + (int) Math.pow(2, d-1) - x/2;
            q.addFirst(x);
            d--;
        } 
        return q;
    }
}

复杂度分析

  • 时间复杂度:O(...)O(...)
  • 空间复杂度:O(d)O(d)
版权声明:本文为qq_43539599原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
本文链接:https://blog.csdn.net/qq_43539599/article/details/106932183