二叉树

二叉树（binary tree）是指树中节点的度不大于2的有序树，它是一种最简单且最重要的树。

介绍

二叉树的递归定义为：二叉树是一棵空树，或者是一棵由一个根节点和两棵互不相交的，分别称作根的左子树和右子树组成的非空树；左子树和右子树又同样都是二叉树。

• golang 示例

/**
 * Definition for a binary tree node.
 */
type TreeNode struct {
	Val   int
	Left  *TreeNode
	Right *TreeNode
}

遍历方式

• 前序遍历：根节点 - 左子树 - 右子树
• 中序遍历：左子树 - 根节点 - 右子树
• 后序遍历：左子树 - 右子树 - 根节点

二叉搜索树

定义如下：

• 节点的左子树只包含 小于 当前节点的数
• 节点的右子树只包含 大于 当前节点的数
• 所有左子树和右子树自身必须也是二叉搜索树