Repository navigation
94. 二叉树的中序遍历 #13
Description
周树人先生曾经说过：学好树，数据结构与算法你就掌握了一半！
食堂老板(童欧巴)：就算我们作为互联网浪潮中的叶子结点，也需要有蚍蜉撼树的精神，就算蚍蜉撼树是自不量力。因为就算终其一生只是个普通人，但你总不能为了成为一个普通人而终其一生吧。
今日菜谱，蚂蚁上树，下面介绍一下演员。
树的相关名词科普
- 根节点
- 叶子节点
- 父节点
- 子节点
- 兄弟节点
- 高度
- 深度
- 层
A 是 根节点。C、D、F、G 是 叶子节点。A 是 B 和 E 的 父节点。B 和 E 是 A 的 子节点。B、E 之间是 兄弟节点。
高度、深度、层 如上图所示。
为了方便理解记忆，高度 就是抬头看，深度 就是低头看。
与 高度、深度 不同，层 类比盗梦空间里的楼，楼都是从 1 层开始计算，盗梦空间中的楼颠倒过来，从上往下。
中序遍历：先打印当前节点的左子树，再打印当前节点，最后打印当前节点的右子树 (CBDAFEG)
const inorderTraversal = function(root) {
const result = [];
function pushRoot(root) {
if (root !== null) {
if (root.left !== null) {
pushRoot(root.left);
}
result.push(root.val);
if (root.right !== null) {
pushRoot(root.right);
}
}
}
pushRoot(root);
return result;
};
- 时间复杂度: O(n)
- 空间复杂度: O(n)
Activity
yuetong3yu commentedon Mar 4, 2021
遍历实现
中序的二叉树遍历相较于前序和后序略有不同