《恋上数据结构与算法一》笔记（6.2）二叉树面试题
2020-03-01 本文已影响0人
路飞_Luck
目录
一 如果一棵完全二叉树有768个节点，求叶子节点的个数
假设叶子节点个数为 n0，度为1的节点个数为 n1，度为2的节点个数为 n2。
总节点个数 n = n0 + n1 + n2，并且 n0 = n2 + 1
n = 2n0 + n1 - 1
完全二叉树的 n1，要么为0，要么为1
1. n1为1时，n = 2n0，n必然是偶数
2. 叶子节点个数为 n0 = n / 2，非叶子节点个数 n1 + n2 = n /2
3. n1 为0时， n = 2n0 -1，n必然是奇数
4. 叶子节点个数 n0 = (n + 1) / 2，非叶子节点个数 n1 + n2 = (n - 1) / 2
叶子节点个数 n0 = floor((n + 1) / 2) = celling(n / 2)
非叶子节点个数 n1 + n2 = floor(n / 2) = celling((n - 1) / 2)
因此叶子节点个数为 384
二 常见算法面试题
- 二叉树的前序遍历 (递归+迭代)
- 二叉树的中序遍历 (递归+迭代)
- 二叉树的后序遍历 (递归+迭代)
- 二叉树的层次遍历 (迭代)
- 二叉树的最大深度 (递归+迭代)
- 二叉树的层次遍历II
- 二叉树最大宽度
- N叉树的前序遍历
- N叉树的后序遍历
- N叉树的最大深度
- 二叉树展开为链表
- 从中序与后序遍历序列构造二叉树
- 从前序与中序遍历序列构造二叉树
- 根据前序和后序遍历构造二叉树
- 对称二叉树
本文会持续更新中，更多精彩内容敬请期待。
本文参考 MJ老师的 恋上数据结构与算法
本人技术水平有限，如有错误欢迎指正。
书写整理不易，您的打赏点赞是对我最大的支持和鼓励，欢迎点赞打赏。
