IT数码 购物 网址 头条 软件 日历 阅读 图书馆
TxT小说阅读器
↓语音阅读,小说下载,古典文学↓
图片批量下载器
↓批量下载图片,美女图库↓
图片自动播放器
↓图片自动播放器↓
一键清除垃圾
↓轻轻一点,清除系统垃圾↓
开发: C++知识库 Java知识库 JavaScript Python PHP知识库 人工智能 区块链 大数据 移动开发 嵌入式 开发工具 数据结构与算法 开发测试 游戏开发 网络协议 系统运维
教程: HTML教程 CSS教程 JavaScript教程 Go语言教程 JQuery教程 VUE教程 VUE3教程 Bootstrap教程 SQL数据库教程 C语言教程 C++教程 Java教程 Python教程 Python3教程 C#教程
数码: 电脑 笔记本 显卡 显示器 固态硬盘 硬盘 耳机 手机 iphone vivo oppo 小米 华为 单反 装机 图拉丁
 
   -> 数据结构与算法 -> LeetCode--1104. 二叉树寻路 -> 正文阅读

[数据结构与算法]LeetCode--1104. 二叉树寻路

1104. 二叉树寻路

前置知识点:

二叉树的性质
性质1:二叉树第i层上的结点数目最多为 2{i-1} (i≥1)。
性质2:深度为k的二叉树至多有2{k}-1个结点(k≥1)。
性质3:包含n个结点的二叉树的高度至少为log2 (n+1)。
性质4:在任意一棵二叉树中,若终端结点的个数为n0,度为2的结点数为n2,则n0=n2+1。

数组存放二叉树的性质:
设某个节点索引值为index,则节点的
左子节点索引为:2index+1
右子节点索引为:2index+2
父节点索引为:(index-1)/2

Java中只存在计算自然对数的函数,如何计算log2?
换底公式:logx(y) =loge(y) / loge(x)

思路:

  1. 计算节点所属的层次
  2. 计算节点的父节点的数值
  3. 翻转父节点的数值:翻转后的父节点数值 = 父节点所在层最大值 + 最小值 - 翻转前父节点的值
  4. 存放当前节点数值,将当前节点数值更新为翻转后的父节点数值,前进到父节点的层次

注意:

  1. 当前节点所在层最小值与最大值:int min= (int) Math.pow(2,k - 1), max= (int) (Math.pow(2,k)-1)
  2. 前一节点所在层最小值与最大值:int min= (int) Math.pow(2,k - 2), max= (int) (Math.pow(2,k - 1)-1)
  3. Math.floor(Math.log(value) / Math.log(2.0)) 计算层次后需要向下取整,但是2的0次方是第一层,需要在获取对数值后再+1
  4. log(0) == 1, 对于常见的对数,可以剪枝增加速度(此处不做优化)
public class Solution1104 {
	public List<Integer> pathInZigZagTree(int label) {
		// 计算 label 的 层次
		int k = logBase2FloorNum(label) + 1;
		List<Integer> res =  Arrays.asList(new Integer[k]);
		int tempNum = label;

		for (;  k > 1; k--) {
			// 计算父亲节点数值
			res.set(k - 1, tempNum);
			// 计算翻转节点的数值
			int min= (int) Math.pow(2,k - 2), max= (int) (Math.pow(2,k - 1)-1);
			tempNum = max + min - (tempNum >> 1);
		}
		res.set(0, 1);
		return res;
	}

	public int logBase2FloorNum(int value) {
		if (value == 1) {
			return 0;
		}
		return (int) Math.floor(Math.log(value) / Math.log(2.0));
	}

	public static void main(String[] args) {
		Solution1104 solution1104 = new Solution1104();
		System.out.println(solution1104.pathInZigZagTree(1));
		System.out.println(solution1104.pathInZigZagTree(14));
		System.out.println(solution1104.pathInZigZagTree(16));
	}
}
  数据结构与算法 最新文章
【力扣106】 从中序与后续遍历序列构造二叉
leetcode 322 零钱兑换
哈希的应用:海量数据处理
动态规划|最短Hamilton路径
华为机试_HJ41 称砝码【中等】【menset】【
【C与数据结构】——寒假提高每日练习Day1
基础算法——堆排序
2023王道数据结构线性表--单链表课后习题部
LeetCode 之 反转链表的一部分
【题解】lintcode必刷50题<有效的括号序列
上一篇文章      下一篇文章      查看所有文章
加:2021-07-31 16:53:22  更:2021-07-31 16:54:48 
 
开发: C++知识库 Java知识库 JavaScript Python PHP知识库 人工智能 区块链 大数据 移动开发 嵌入式 开发工具 数据结构与算法 开发测试 游戏开发 网络协议 系统运维
教程: HTML教程 CSS教程 JavaScript教程 Go语言教程 JQuery教程 VUE教程 VUE3教程 Bootstrap教程 SQL数据库教程 C语言教程 C++教程 Java教程 Python教程 Python3教程 C#教程
数码: 电脑 笔记本 显卡 显示器 固态硬盘 硬盘 耳机 手机 iphone vivo oppo 小米 华为 单反 装机 图拉丁

360图书馆 购物 三丰科技 阅读网 日历 万年历 2024年11日历 -2024/11/25 16:55:44-

图片自动播放器
↓图片自动播放器↓
TxT小说阅读器
↓语音阅读,小说下载,古典文学↓
一键清除垃圾
↓轻轻一点,清除系统垃圾↓
图片批量下载器
↓批量下载图片,美女图库↓
  网站联系: qq:121756557 email:121756557@qq.com  IT数码