树--平衡二叉树、获取所有路径

2022-01-19 本文已影响0人习惯水文的前端苏

$\bullet$ 平衡二叉树

$\ast$ 题号

$\ast$ 概念

左子树与右子树的高度差的绝对值小于等于1

$\ast$ 思路

树高即树深

由于一棵树是由n颗子树构成，故需要递归向下判断每一颗树是否平衡，只有每一颗子树平衡了，以该子树的父节点为根的树才是平衡树

"平"的关键是看其左子树的树深与右子树的树深

$\ast$ 实现一

$\ast$ 实现二

实现一中，越接近叶子节点的节点被重复遍历计算的次数越多

在后序遍历中，由于是先遍历左右子树，故在访问到根时，有能力收集子树信息

$\bullet$ 搜索二叉树

$\ast$ 题号

$\ast$ 思路

将一条路径的值在每一次递归序中拼接并传递给下一个递归序

$\ast$ 实现

上一篇下一篇

猜你喜欢

热点阅读