一、二叉树基础知识

二叉树种类

• 满二叉树：如果一棵二叉树只有度为0的结点和度为2的结点，并且度为0的结点在同一层上，则这棵二叉树为满二叉树。
• 完全二叉树：在完全二叉树中，除了最底层节点可能没填满外，其余每层节点数都达到最大值，并且最下面一层的节点都集中在该层最左边的若干位置。若最底层为第 h 层，则该层包含 1~ 2^h -1 个节点。
• 二叉搜索树：只有二叉搜索树有数值。二叉搜索树为有序树。
  若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值；
  若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值；
  它的左、右子树也分别为二叉排序树
• 平衡二叉搜索树（AVL树）：它是一棵空树或它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树。
  注：C++中map、set、multimap，multiset的底层实现都是平衡二叉搜索树，所以map、set的增删操作时间时间复杂度是logn，注意我这里没有说unordered_map、unordered_set，unordered_map、unordered_map底层实现是哈希表。

二叉树存储方式

• 链式存储：使用指针
• 顺序存储：如果父节点的数组下标是 i，那么它的左孩子就是 i * 2 + 1，右孩子就是 i * 2 + 2。

二叉树遍历方式

• 深度优先遍历：前序遍历、中序遍历、后序遍历
• 广度优先遍历：层次遍历

二叉树c++定义

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

二、二叉树的遍历

• 递归遍历
• 非递归遍历

1.前序遍历

• 遍历顺序：前左右
• 非递归利用栈先进后出，即先将右节点压入栈内，再将左节点压入栈内。弹栈时即可达到前左右的遍历顺序。
• 由于栈顶节点在不断变化，使用临时节点tempp栈顶元素。
• 需要初始化一个栈stack和vector,stack存储节点，vector存储节点值。
• 边界条件：如果root为空节点，返回v或者返回{}；

class Solution {
public:
    vector<int> preorderTraversal(TreeNode* root) {
        vector<int>v;
        stack<TreeNode *>s;
        if(root==nullptr){
            return {};
        }
        s.push(root);
        while(!s.empty()){
            TreeNode *temp=s.top();
            v.push_back(temp->val);
            s.pop();
            if(temp->right){
                s.push(temp->right);
            }
            if(temp->left){
                s.push(temp->left);
            }
        }
        return v;
    }
}

2.中序遍历

- 遍历顺序：左前右

• 创建一个cur指针，其作用是先遍历到树的底部再弹栈。
• while循环条件为cur||!s.empty()，和前序遍历比多了cur||,因为从一开始并没有将root压入栈内，所以一开始是空栈，而cur初始时等于root节点。

class Solution{
    public:
        vector<int>inorderTraversal(TreeNode*root)
        {
            vector<int>v;
            stack<TreeNode *>s;
            if(root==nullptr){
                return {};
            }
            TreeNode *cur=root;
            //一开始为空栈避免直接退出循环。
            while(cur||!s.empty())
            {
                if(cur){
                    s.push(cur);
                    cur=cur->left;
                }
                else{
                    cur=s.top();
                    s.pop();
                    v.push_back(cur->val);
                    cur=cur->right;
                }
            }
            return v;   
        }
};

3.后序遍历

• 遍历顺序：左右前
• 想想前序遍历和后序遍历顺序的关系。
• 先压左节点，再压右节点，再reverse数组v。

class Solution{
private:
    vector<int>v;
    public:
    vector<int> postorderTraversal(TreeNode* root)
    {
        vector<int>v;
        stack<TreeNode *>s;
        if(root==nullptr)
        {
            return {};
        }
        s.push(root);
        while(!s.empty())
        {
            TreeNode *temp=s.top();
            s.pop();
            v.push_back(temp->val);
            if(temp->left){
                s.push(temp->left);
            }
            if(temp->right){
                s.push(temp->right);
            }
        }
        reverse(v.begin(),v.end());
        return v;
    }
};

4.层序遍历

• 遍历顺序：一层一层进行遍历

• 利用队列先进先出

class Solution {
vector<vector<int>>res;
public:
    vector<vector<int>> levelOrder(TreeNode* root) {
        if(root==nullptr){
            return {};
        }
        queue<TreeNode *>q;
        q.push(root);

        while(!q.empty()){
        vector<int>v;
        int size=q.size();
        for(int i=0;i<size;i++){
            TreeNode *temp=q.front();
            v.push_back(temp->val);
            q.pop();
            if(temp->left){
                q.push(temp->left);
            }
            if(temp->right){
                q.push(temp->right);
            }
        }
        res.push_back(v);
        }
    return res;
    }
};

三、二叉树的属性

求普通二叉树的属性一般使用后序，通过递归函数的返回值做计算。

1.对称二叉树

• 采用后序遍历方式，中节点用来判断左树和右树是否对称，每一层递归使用bool值进行接收。
• compare函数比较左树和右树是否对称，传入参数有left和right，递归终止条件有：if(left&&!right){ return false; } else if(!left&&right){ return false; } else if(!left&&!right){ return true; } else if(left&&right&&left->val!=right->val){ return false; }

class Solution {
public:
    bool compare(TreeNode *left,TreeNode *right){
        if(left&&!right){
            return false;
        }
        else if(!left&&right){
            return false;
        }
        else if(!left&&!right){
            return true;
        }
        else if(left&&right&&left->val!=right->val){
            return false;
        }
        bool bool_left=compare(left->right,right->left);
        bool bool_right=compare(left->left,right->right);
        bool is_same=bool_left&&bool_right;
        return is_same;
    }
    bool isSymmetric(TreeNode* root) {
        if(root==nullptr){
            return true;
        }
        return  compare(root->left,root->right);
    }
};

2.二叉树的最大深度

• 首先区分高度和深度的概念，求深度应该是用前序遍历，但是求二叉树的最大深度等同于求二叉树的高度，因此使用后序遍历即可。
• 先递归到左树的最底部求出左树的高度，再递归到右树的最底部求出右树的高度，中节点处理逻辑为比较左树和右树的高度大小返回高度最高值。
• 递归终止条件为if(root==nullptr){ return 0; }，遇到空节点返回数值0

class Solution {
public:
    int maxDepth(TreeNode* root) {
        if(root==nullptr){
            return 0;
        }
        int leftdepth=1+maxDepth(root->left);
        int rightdepth=1+maxDepth(root->right);
        int depth=max(leftdepth,rightdepth);
        return depth;
    }

3.二叉树的最小深度

• 采用后序遍历方式，求深度就是求高度。
• 中节点处理逻辑和求最大深度逻辑不同，要考虑左数和右树分别有一个不存在的时候怎么求深度。

class Solution {
public:
    int minDepth(TreeNode* root) {
        if(root==nullptr){
            return 0;
        }
        int leftdepth=minDepth(root->left);
        int rightdepth=minDepth(root->right);
        if(root->left&&!root->right){
            return 1+leftdepth;
        }
        if(!root->left&&root->right){
            return 1+rightdepth;
        }
        return 1+min(leftdepth,rightdepth);
    }
};

4.完全二叉树的节点个数

• 采用后序遍历方式
• 注意在哪个位置加1，不然容易节点数翻一倍。
• 叶子节点其实就是一个中节点node。左孩子为空，右孩子为空，0+0+1=1。

class Solution {
public:
    int countNodes(TreeNode* root) {
        if(root==nullptr){
            return 0;
        }
        int leftnodes=countNodes(root->left);
        int rightnodes=countNodes(root->right);
        int node=leftnodes+rightnodes+1;
        return node;
    }
};

5.平衡二叉树

平衡二叉树

• 高度是int，而要返回的是bool型，怎么写函数
• 如果高度差大于1，则返回-1

class Solution {
public:
    int getheight(TreeNode *root){
        if(root==nullptr){
            return 0;
        }
        int leftheight=getheight(root->left);
        if(leftheight==-1){
            return -1;
        }
        int rightheight=getheight(root->right);
        if(rightheight==-1){
            return -1;
        }
        if(abs(leftheight-rightheight)>1){
            return -1;
        }
        else{
            return 1+max(leftheight,rightheight);
        }
    }
    bool isBalanced(TreeNode* root) {
       return getheight(root)==-1?false:true;
    }
};

6.二叉树的所有路径

6.二叉树的所有路径

• 前序遍历