二叉树基础知识

二叉树种类

满二叉树
满二叉树：如果一棵二叉树只有度为0和度为2的结点，并且度为0的结点在同一层上，则这棵二叉树为满二叉树（子节点要么为0，要么为2）
若满二叉树的深度为k（即k层，从1开始），则其节点个数为：2^k-1
完全二叉树
完全二叉树：从上到下，从左到右，都是连续的。 满二叉树一定是完全二叉树。
优先级队列是一个堆，堆就是完全二叉树
二叉搜索树
节点是有顺序的，
若左子树不为空，左子树上节点的值小于根节点，
若右子树不为空，右子树上节点的值大于根节点
平衡二叉（搜索）树
它是一颗空树或左右子数的高度差绝对值不超过1.并且左右子数都是一颗平衡二叉（搜索）树。
map、set、multimap、multiset 的底层实现都是平衡二叉树，所以是有序的。

二叉树的存储方式

链式存储
使用指针来连接左子树和右子树，一般用链式
线性存储（内存连续分布）
使用数组来村存储
计算孩子节点：若父节点数组下标为n，则左孩子节点为2n+1，右孩子节点为2n+2；

二叉树的遍历

二叉树主要有两种遍历方式：

1. 深度优先遍历：先往深走，遇到叶子节点再往回走。
   1.前序遍历（递归法，迭代法（就是非递归方法）） 中左右
   2.中序遍历（递归法，迭代法）左中右
   3.后序遍历（递归法，迭代法）左右中
   深度优先遍历，一般使用递归的方式来实现，使用栈结构，栈就是递归的一种实现结构，
2. 广度优先遍历：一层一层的去遍历。
   层次遍历（迭代法）
   广度优先遍历，一般使用队列来实现

二叉树的递归遍历

递归算法三要素

1. 确定递归函数的参数和返回值
2. 确定递归函数的终止条件
3. 确定单层递归条件

//Definition for a binary tree node.
 struct TreeNode {
      int val;
      TreeNode *left;
      TreeNode *right;
      TreeNode() : val(0), left(nullptr), right(nullptr) {}
      TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
      TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 };

题目：144.二叉树的前序遍历

题目：145.二叉树的后序遍历
题目：94.二叉树的中序遍历

思路：

0. 递归三要素，参数返回值，终止条件，单层循环

代码：

class Solution {
public:
    void Traversal(TreeNode *cur,vector<int> &vec){  //注意vector是引用
        if(cur==nullptr)
            return;
        vec.push_back(cur->val);
        Traversal(cur->left,vec);
        Traversal(cur->right,vec);
    }

    vector<int> preorderTraversal(TreeNode* root) {
        vector<int> result; 
        Traversal(root,result);
        return result;
    }
};

二叉树的层序遍历

题目：102.二叉树的层序遍历

思路：

0.确定二维数组存储节点的值，使用队列进行遍历，队首弹出存储过值的节点，队尾添加被弹出节点的左子树、右子树，计算每层的大小，在队列中弹出对应数量，每一层的值存入一个数组中，

代码：

class Solution {
public:
    vector<vector<int>> levelOrder(TreeNode* root) {
        vector<vector<int>> result;
        queue<TreeNode*> que; //这里是*
        if(root!=nullptr)
            que.push(root) ; //编译报错 root可能为空
        while(!que.empty()){
            vector<int> vec;
            int size=que.size();
            while(size--){
                TreeNode* node=que.front();
                vec.push_back(node->val);
                if(node->left!=nullptr)
                    que.push(node->left);
                if(node->right!=nullptr)
                    que.push(node->right);
                que.pop();
            } 
            result.push_back(vec);
        }
        return result;
    }
};

题目：107.二叉树的层序遍历Ⅱ

思路：

0. 层序遍历，然后翻转，计算数组大小，首尾对调
1. 翻转直接用reverse 因为vector的定义是 vector<vector<int>> result; result的元素就是vector

题目：199.二叉树的右视图

思路：

0. 一直遍历右子树，递归，但不行，不一定从右边看到的都是右子树
1. 同上，层序遍历，结果只保存每层遍历的最后一个值。

坑：

队列定义的时候，注意类型。不要默认是int
queue<TreeNode*> queue;

题目：637.二叉树的层平均值

思路：

同上，每层结果取平均值

坑：

报错，超出内存，忘了出队。

题目：429.N叉树的层序遍历

思路：

类似，每个节点，判断孩子数是否全部被添加完

题目：515.在每个树行中找最大值

思路：

同上，遍历的时候，挨个比较，保存最大值

题目：116.填充每个节点的下一个右侧节点指针

思路：

这个是定义的“完美”二叉树
遍历时，保存上一个节点，判断当前节点是否有左孩子，没有就右孩子，使其指向下一个右侧节点，当size==0时，指向null

题目：117.填充每个节点的下一个右侧节点指针II

思路：

这个是二叉树
同上

题目：104.二叉树的最大深度

思路：

0.0递归，一直找子树，直到为null，返回，记录次数
0.1栈存储，遍历到null的时候计算栈长度
返回值是长度，参数是节点和&存储长度的变量
终止条件是节点的孩子数为0
单层循环，中序遍历，
啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊，有简单的啊啊啊啊啊，吗喽心塞塞.jpg
1.层序遍历，计算层数，使用迭代法（非递归），深度嘛，就是层数啊

题目：111.二叉树的最小深度

思路：

同上，不过左右孩子都为空时，才是遍历到叶子结点了

今日总结

二叉树分类，深度和广度遍历