鱼C论坛

 找回密码
 立即注册
查看: 1828|回复: 0

[技术交流] C++刷LeetCode(1104. 二叉树寻路)【二叉树】【位运算】

[复制链接]
发表于 2021-7-29 20:48:26 | 显示全部楼层 |阅读模式

马上注册,结交更多好友,享用更多功能^_^

您需要 登录 才可以下载或查看,没有账号?立即注册

x
题目描述:
  1. 在一棵无限的二叉树上,每个节点都有两个子节点,树中的节点 逐行 依次按 “之” 字形进行标记。

  2. 如下图所示,在奇数行(即,第一行、第三行、第五行……)中,按从左到右的顺序进行标记;

  3. 而偶数行(即,第二行、第四行、第六行……)中,按从右到左的顺序进行标记。



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

  5.  

  6. 示例 1:

  7. 输入:label = 14
  8. 输出:[1,3,4,14]
  9. 示例 2:

  10. 输入:label = 26
  11. 输出:[1,2,6,10,26]
  12.  

  13. 提示:

  14. 1 <= label <= 10^6

  15. 来源:力扣(LeetCode)
  16. 链接:https://leetcode-cn.com/problems/path-in-zigzag-labelled-binary-tree
  17. 著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
复制代码


  1. class Solution {
  2. public:
  3.     vector<int> pathInZigZagTree(int label) {
  4.         vector <int> ans;
  5.         while(label) {
  6.             ans.push_back(label);
  7.             label >>= 1;
  8.         }
  9.         reverse(ans.begin(), ans.end());
  10.         int l, r, deep = ans.size();
  11.         for(int i = 0; i < deep; i++) {
  12.             if((deep & 1) == (i & 1)){
  13.                 l = (1 << i);
  14.                 r = l + l - 1;
  15.                 ans[i] = r - ans[i] + l;
  16.             }
  17.         }
  18.         return ans;
  19.     }
  20. };
复制代码



参考链接:https://leetcode-cn.com/problems ... 0-jie-fa-wei-p3ik1/

本帖被以下淘专辑推荐:

想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复

使用道具 举报

您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

小黑屋|手机版|Archiver|鱼C工作室 ( 粤ICP备18085999号-1 | 粤公网安备 44051102000585号)

GMT+8, 2024-3-29 13:36

Powered by Discuz! X3.4

© 2001-2023 Discuz! Team.

快速回复 返回顶部 返回列表