二叉树

树

基础遍历

递归遍历

例： 1

​ 2 3

​ 4 5 6 7

void Order(node *head){
    if(head==null) return;
    //(1)
    Order(head->left);
    //(2)
    Order(head->right);
    //(3)
}

递归序(访问结点的顺序)：1 2 4 4 4 2 5 5 5 2 1 3 6 6 6 3 7 7 7 1

cout<<head->data<<" ";//打印语句位置

先序遍历：第一次访问打印 (1)

中序遍历：第二次访问打印(2)

后序遍历：第三次访问打印(3)

迭代遍历

三种遍历都是用的栈

先序遍历

144. 二叉树的前序遍历

1. 头先进栈
2. 当栈不为空，弹出cur
   1. 打印cur
   2. cur右进栈，左进栈

后序遍历

145. 二叉树的后序遍历

1. 头先进栈
2. 当栈不为空，弹出cur
   1. 打印cur
   2. cur左进栈，右进栈
3. 翻转数组

中序遍历

94. 二叉树的中序遍历

1. 整棵树左边界进栈
2. 弹出，打印cur
3. cur右子树的左边界进栈

宽度优先遍历/层次遍历

宽度优先遍历用队列

1. 头结点先进队
2. 循环
   1. 弹出就打印cur
   2. 先放左再放右

求二叉树最大宽度

• 法1：哈希表：（head，1）//第一层

  curlevel,curlevelnode,max

  弹出结点=当前层，node++

  else 说明进入下一层了

  ——>需要一个哈希表，进队列的时候(left，level+1);

• 法2：队列

常见概念

搜索二叉树

每一个节点大于左子树，小于右子树

判断：中序遍历，输出一定是升序

98. 验证二叉搜索树

完全二叉树

958. 二叉树的完全性检验

满二叉树

平衡二叉树

任何节点左树和右树的高度差都不超过1

二叉树的递归套路

1. 列出所有的可能性
2. 整理需要左树、右树提供的信息，封装为结构体，作为返回值（左右子树返回值得是一样的）
3. 函数结构
   1. 空树情况（如果情况比较奇怪，返回NULL，调用的时候再讨论）
   2. 处理左树，处理右树
   3. 根据左右子树信息，处理本树
   4. 返回

递归套路可以解决一切树型dp问题：问题可以通过向左子树和右子树要信息解决

但要具体问题具体分析，也不是所有问题都能用套路