树结构

struct TreeNode {
 int val;
 TreeNode *left;
 TreeNode *right;
 TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};

二叉树相关属性解释：

• 结点：包含一个数据元素及若干指向子树分支的信息。

• 结点的度：一个结点拥有子树的数目称为结点的度。

• 叶子结点：也称为终端结点，没有子树的结点或者度为零的结点。

• 分支结点：也称为非终端结点，度不为零的结点称为非终端结点。

• 树的度：树中所有结点的度的最大值。

• 结点的层次：从根结点开始，假设根结点为第1层，根结点的子节点为第2层，依此类推，如果某一个结点位于第L层，则其子节点位于第L+1层。

• 树的深度：也称为树的高度，树中所有结点的层次最大值称为树的深度。

• 有序树：如果树中各棵子树的次序是有先后次序，则称该树为有序树。

• 无序树：如果树中各棵子树的次序没有先后次序，则称该树为无序树。

• 二叉树遍历方式分为三种(根的顺序,左右固定)

• • 前序遍历（根左右）： 访问根结点，再访问左子树、再访问右子树。
  • 中序遍历（左根右）： 先访问左子树，再访问根结点、再访问右子树。
  • 后续遍历（左右根）： 先访问左子树，再访问右子树，再访问根结点。

• 前序:每次输出根节点,然后访问左,左变成根节点

  中序:先把左递归完然后回溯,依次输出左,回溯一下输出根,再输出右

  后序:访问根结点的操作发生在遍历其左右子树之后。就是左右都没了才访问根

• 二叉树节点的深度：指从根节点到该节点的最长简单路径边的条数或者节点数（取决于深度从0开始还是从1开始）

• 二叉树节点的高度：指从该节点到叶子节点的最长简单路径边的条数或者节点数（取决于高度从0开始还是从1开始）

• 根节点的高度就是二叉树的最大深度