一、结构体定义

struct TreeNode{
    int val;
    TreeNode *left;
    TreeNode *right;
}

二、二叉树遍历

1、先序遍历

//递归
void preOrder(TreeNode *root){
    if(!root) return;
    cout << root -> val << ' ';
    preOrder(root -> left);
    preOrder(root -> right);
}

//非递归(借用栈)
void preOrder(TreeNode *root){
    stack<TreeNode> s;
    s.push(root);

    while(!is_empty()){
        TreeNode *node = s.top();
        cout << node -> val << ' ';
        s.pop()

        if(node -> right) s.push(node -> right);
        if(node -> left) s.push(node -> left);
    }
}

2、中序遍历

//递归
void inOrder(TreeNode *root){
    if(!root) return;

    preOrder(root -> left);
    cout << root -> val << ' ';
    preOrder(root -> right);
}

//非递归(借助栈)
void preOrder(TreeNode *root){
    stack<TreeNode> s;
    TreeNode *t = root;

    while(t || !is_empty()){

        while(t){//将当前结点所有左节点入栈
            s.push(t);
            t = t -> left;
        }

        t = s.top();

        cout << node -> val << ' ';
        s.pop()

        t = t -> right;//遍历当前结点右子树
    }
}

3、后序遍历

//递归
void postOrder(TreeNode *root){
    if(!root) return;

    preOrder(root -> left);
    preOrder(root -> right);
    cout << root -> val << ' ';
}

//非递归(借助栈)
void postOrder(TreeNode *root){
    stack<TreeNode> s;
    TreeNode *t = root;
    TreeNode *p = nullptr;

    while(t || !is_empty()){
        while(t){
            s.push(t);
            t = t -> left;
        }

        t = s.top();
        if(!t -> right || p == t){//若当前结点没有右子树或已访问过
            cout << node -> val << ' ';
            s.pop();
            p = t;
            t = nullptr;
        }else{//否则遍历右子树
            t = t -> right;
        }
    }
}

4、层次遍历（借助队列）

层次遍历算法思想：
逆序层次遍历算法思想：利用队列，先将二叉树按照正序层次遍历，然后存储在栈中，最后输出即可

//层次遍历（借助队列)
void levelOrder(TreeNode *root){
    queue<TreeNode*> q;
    q.push(root);

    while(!q.empty()){
        TreeNode *t = q.front();
        q.pop();

        cout << t -> val << ' ';
        if (t->left) q.push(t->left);
        if (t->right) q.push(t->right);
    }
}

//逆序层次遍历
void invertLevelOrder(TreeNode* root){
    quque<TreeNode*> q;
    stack<TreeNode*> s;
    q.push(root);

    while(!q.empty()){
        TreeNode *t = q.front();
        q.pop();
        s.push(t);

        if(t -> left) q.push(t -> left);
        if(t -> right) q.push(t -> right);
    }

    while(!s.empth){
        cout << s.top() << " ";
        s.pop();
    }
}

三、应用

1、求树高

递归算法思想：递归左右子树，取最大值；
非递归算法思想：利用层次遍历，每层遍历设置n记录该层节点数，将该层结点出队，遍历其孩子节点入队，遍历完一层后height+1

//递归
int height(TreeNode *root){
    if(!root) return 0;
    return max(height(root -> left), height(root -> right)) + 1;
}

//非递归
int height(TreeNode *root){
    queue<TreeNode*> q;
    q.push(root);
    int height = 0;

    while(q.size){
        int n = q.size();
        while(n--){
            TreeNode *t = q.front();
            q.pop();
            if(t -> left) q.push(t -> left);
            if(t -> right) q.push(t -> right);
        }
        height ++;
    }

    return height;
}

2、判断是否为完全二叉树

算法思想：利用层次遍历，若在遍历到空结点之后还有结点，则不是二叉树。

bool ifComlpeteTree(TreeNode *root){
    queue<TreeNode*> q;
    q.push(root);
    bool leaf = false;

    while(!q.empty()){
        TreeNode *t = q.front();
        q.pop();

        if(!t){//遇到空结点。
            leaf = true;
            continue;
        }

        if(leaf && t) return false;//空结点后还有结点,不是二叉树

        if (t->left) q.push(t->left);
        if (t->right) q.push(t->right);
    }

    return true;
}

3、计算双节点个数

算法思想：利用递归，遍历每个结点，在遍历时判断当前结点是否同时有左子树和右子树。

int res = 0;
int fun(TreeNode *root){
    if(!root) return 0;

    if(root -> left && root -> right) res++;

    fun(roor -> left);
    fun(root -> right);
}

4、交换所有结点的左右子树

算法思想：递归遍历每一个结点，将当前遍历结点的左右子树进行交换。

int res = 0;
int fun(TreeNode *root){
    if(!root) return 0;

    if(root -> left && root -> right){
        TreeNode *t = nullptr;
        t = root -> left;
        root -> left = root -> right;
        root -> right = t;
    }

    //或使用swap函数
    swap(root -> left, root -> right);

    fun(roor -> left);
    fun(root -> right);
}

5、先序遍历序列中第 k(1≤k≤二叉树中结点个数)个结点的值。

int res = 0, k = 4, i = 0;
void dfs(TreeNode* root)
{
    i ++;
    if (i == k) res = root->val;
    if (root->left) dfs(root->left);
    if (root->right) dfs(root->right);
}

6、使用DFS删除以值为x的节点及其子树

void dfs(TreeNode* &root, int x) // 这里使用引用符号&是因为我们要修改root本身（即修改指针的指向）
{
    if (!root) return;  // 如果当前节点为空，直接返回

    // 如果当前节点的值等于x，删除当前节点（置为NULL），并返回
    if (root->val == x) 
    {
        root = NULL;  // 通过引用修改父节点的指针，将其指向NULL，删除该子树
        return;
    }

    // 递归处理左右子树
    dfs(root->left, x);
    dfs(root->right, x);
}