原题链接

周树人先生曾经说过：学好树，数据结构与算法你就掌握了一半！

食堂老板(童欧巴)：就算我们作为互联网浪潮中的叶子结点，也需要有蚍蜉撼树的精神，就算蚍蜉撼树是自不量力。因为就算终其一生只是个普通人，但你总不能为了成为一个普通人而终其一生吧。

今日菜谱，蚂蚁上树，下面介绍一下演员。

树的相关名词科普

• 根节点
• 叶子节点
• 父节点
• 子节点
• 兄弟节点
• 高度
• 深度
• 层

A 是根节点。C、D、F、G 是叶子节点。A 是 B 和 E 的父节点。B 和 E 是 A 的子节点。B、E 之间是兄弟节点。

高度、深度、层 如上图所示。

为了方便理解记忆，高度 就是抬头看，深度 就是低头看。

与 高度、深度 不同，层 类比盗梦空间里的楼，楼都是从 1 层开始计算，盗梦空间中的楼颠倒过来，从上往下。

中序遍历：先打印当前节点的左子树，再打印当前节点，最后打印当前节点的右子树 (CBDAFEG)

constinorderTraversal=function(root){constresult=[];functionpushRoot(root){if(root!==null){if(root.left!==null){pushRoot(root.left);}result.push(root.val);if(root.right!==null){pushRoot(root.right);}}}pushRoot(root);returnresult;};

• 时间复杂度: O(n)
• 空间复杂度: O(n)