二叉树

二叉树是常见的底层数据结构，也是递归的重要应用场景

1 种类

• 满二叉树：所有节点都齐全的一个二叉树
• 完全二叉树：除了底层全部都满，并且 从左到右 连续有节点，满二叉树一定是完全二叉树
  

  

• 二叉搜索树：搜索效率是 O(log n)，节点元素有顺序，可以是左小右大
• 平衡二叉树：左子树高度和右子树高度差绝对值 小于 1

在 C++ 中 std::set / std::multiset / std::map / std::multimap 都由红黑树（自平衡二叉搜索树）

下方演示了如何判断平衡二叉搜索树

2 存储方式

2.1 链式

使用左右指针即可，如果没有孩子则为 nullptr

代码实现如下：

struct TreeNode {
    int val;                // 节点值
    TreeNode* left;         // 左子节点
    TreeNode* right;        // 右子节点

    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}  // 构造函数
};

2.2 线性

线性存储唯一要注意的就是如何计算左右孩子，（实际上不太会用这种方式存储）

假设根节点是编号 i ，左孩子的 2i + 1， 右孩子 2i + 2

3 遍历方式

3.1 深度优先搜索（DFS）

一般使用的 前中后序遍历都属于 DFS，可以使用递归或者迭代的方式实现，本质是栈 FILO

前中后指的是父节点的访问顺序

1. 前序遍历： 中左右，前序遍历是按照数据结构来顺序处理节点，迭代逻辑最简单
2. 中序遍历：左中右，中序遍历对二叉搜索树有排序的作用
3. 后序遍历：左右中，后序遍历有回溯的功能，能够实现类似从下向上遍历的功能

下面是两种方式实现中序遍历，注意中序遍历能够获得二叉搜索树排序后的结果

#include <vector>
void inorderRecursive(TreeNode* root, std::vector<int>& res) {
    if (!root) return;
    inorderRecursive(root->left, res);
    res.push_back(root->val);
    inorderRecursive(root->right, res);
}

前序遍历的 DFS （迭代）要更加简单一点，因为访问和处理的节点都是同一个

#include <vector>
#include <stack>
using namespace std;

class Solution {
public:
    vector<int> preorderTraversal(TreeNode* root) {
        vector<int> ret;
        if (!root) return ret;
        stack<TreeNode*> stk;
        stk.push(root);

        while (!stk.empty()) {
            TreeNode* curr = stk.top();
            stk.pop();
            ret.push_back(curr->val);

            if (curr->right) stk.push(curr->right);
            if (curr->left)  stk.push(curr->left);
        }
        return ret;
    }
};

后序遍历有两步：

1. 将前序左右子树访问顺序交换： 中左右 -> 中右左
2. 将结果翻转（双指针）： 左右中

中序遍历要复杂一点，需要借助指针深度访问到底，再进行对应处理

// 迭代法中序遍历
#include <stack>
#include <vector>
std::vector<int> inorderIterative(TreeNode* root) {
    std::vector<int> res;
    std::stack<TreeNode*> st;
    TreeNode* curr = root;

    while (curr || !st.empty()) {
        // 一直向左走
        while (curr) {
            st.push(curr);
            curr = curr->left;
        }
        // 访问栈顶节点
        curr = st.top();
        st.pop();
        res.push_back(curr->val);
        // 转向右子树
        curr = curr->right;
    }
    return res;
}

也有一种使用标记法的方式，可以使用同一个代码结构完成 3 种遍历，稍微难理解一点

3.2 广度优先搜索 （BFS）

层序遍历，就是使用迭代法进行，本质是使用队列的 LIFO

注意的是需要记住每一层的队列中的元素个数

#include <vector>
#include <queue>
class Solution {
public:
    vector<vector<int>> levelOrder(TreeNode* root) {
        queue<TreeNode*> q;
        vector<vector<int>> ret;
        if (!root) return ret;
        q.push(root);
        while(!q.empty()) {
            // 取出所有的子节点
            vector<int> ret_layer; 
            int current = q.size();
            for (int i = 0; i < current; i++) {
                TreeNode* cur = q.front();
                q.pop();
                if (cur->left) q.push(cur->left);
                if (cur->right) q.push(cur->right);
                ret_layer.push_back(cur->val);
            }
            ret.push_back(ret_layer);
        }
        return ret;
    }
};

4 题目选取

挑选一些初见不是很顺利的题记录一下

递归的要义：

1. 返回值和输入参数
2. 终止条件
3. 递归细化逻辑

4.1 平衡二叉树（求深度）

力扣平衡二叉树

平衡二叉树是左右子树 高度 差 不大于 1

主要知识点：求 高度 需要使用 后序遍历 ， 求 深度 使用 前序遍历

原因： 后序遍历，根节点最后遍历，层层向上返回，根节点根据左右孩子的数据来计算；反之则是孩子获取到根节点的深度

#include <cmath>
class Solution {
public:
    bool isBalanced(TreeNode* root) {
        if(getHeight (root) >= 0) {
            return true;
        } else {
            return false;
        }
    }

    int getHeight(TreeNode *curr) {
        // 获取高度，如果不平衡直接返回 -1
        // 高度要使用后序遍历
        if (curr == nullptr) return 0;
        
        int left = getHeight(curr->left);
        int right = getHeight(curr->right);

        if (left == -1 || right == -1) return -1;
        if (abs(left - right) > 1) {
            return -1;
        } else {
            return (left > right ? left : right) + 1;
        }
    }
};

4.2 中序后序构造二叉树

总体逻辑是轮流进行分割，需要注意的是先要确定返回条件，设置为 root 节点

1. 后序遍历最后一个就是根节点的值
2. 根据这个值来构造一个节点
3. 根据这个值去将中序数组切割成左右两部分
4. 根据中序的值将后序的左右部分分开
5. 进一步递归（中序左，后序左）（中序右，后序右），分别是左右孩子

注意到这里为了代码可读性，每次都进行一个复制操作。实际可以优化为每次都传递索引值

class Solution {
public:
    TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) {
        if (!postorder.size()) 
            return nullptr;

        return _buildTree(inorder, postorder);
    }

    TreeNode* _buildTree(vector<int> inorder, vector<int> postorder) {
        // 数组为空代表已经完毕
        if (postorder.size() == 0) {
            return nullptr;
        }
        
        // 1 后序遍历最后一个数字取出，构造根节点
        int sz = postorder.size();
        int cut1 = postorder[sz -1];
        postorder.pop_back();
        TreeNode* root = new TreeNode(cut1);

        // 2. 分割中序
        int i = 0;
        for (; i < inorder.size(); i++) {
            if (inorder[i] == cut1)
                break;
        }
        vector<int> in_left(inorder.begin(), inorder.begin() + i);
        vector<int> in_right(inorder.begin() + i + 1, inorder.end());

        // 3. 按照左边 size 分割后序
        vector<int> post_left(postorder.begin(), postorder.begin() + i);
        vector<int> post_right(postorder.begin() + i, postorder.end());

        // 递归并构造
        root->left = _buildTree(in_left, post_left);
        root->right = _buildTree(in_right, post_right);

        return root;
    }
};

4.3 二叉搜索树 BST

判断一个 BST 是否是有效，使用递归

关键在于想清楚 当前最大值的逻辑

class Solution {
public:
    bool isValidBST(TreeNode* root) {
        long long maxVal = LONG_MIN;
        return _isValidBST(root, maxVal);
    }
    
    bool _isValidBST(TreeNode* root, long long& max) {
        if (!root) return true;

        // 中序遍历
        bool left = _isValidBST(root->left, max);
        if (root->val <= max) 
            return false;
        else
            max = root->val;
        bool right = _isValidBST(root->right, max);  

        return left && right;
    }
    
};

4.4 二叉树的最近公共祖先

这道题的回溯返回值很精妙，应该时常复习

因为二叉树只能从根节点从上往下，所以使用回溯的思想，也就是后序遍历

左右子树如果出现了目标元素就返回值，否则返回空；如果一个节点左右子树都出现了返回值，那代表是公共祖先

1. 参数返回：根节点，返回 nullptr或者对应的节点
2. 终止条件：返回节点则继续上报

class Solution {
public:
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        // 终止递归条件：空节点或者已经找到
        if (!root) return nullptr;
        if (root == p || root == q) return root;

        TreeNode* left = lowestCommonAncestor(root->left, p, q);
        TreeNode* right = lowestCommonAncestor(root->right, p, q);

        // 已经找到
        if (left && right) {
            return root;
        }
        // 传递返回已经找到的值, nullptr 也会正确返回
        return left ? left : right;
    }
};

4.5 二叉搜索树的插入

添加节点相对简单，不需要改变原有的树结构

使用递归方法

可能会把方法想的很复杂，但是实际上很简单，记住就行

class Solution {
public:
    TreeNode* insertIntoBST(TreeNode* root, int val) {
        if (root == nullptr) {
            TreeNode* ret = new TreeNode(val);
            return ret;
        }
        if (val > root->val) root->right = insertIntoBST(root->right, val);
        if (val < root->val) root->left = insertIntoBST(root->left, val);
        return root;
    }
};

4.6 删除二叉搜索树的节点

情况很多，比添加复杂得多，需要考虑很多的情况

一共有五种情况：

1. 没有找到，不用删除
2. 删除叶子节点，直接设为 nullptr
3. 左非空右空，将父节点的左孩子指向被删的孩子
4. 左空右非空，同理跳过被删节点直接指向孩子
5. 左右都非空，最复杂的，让右子树继位，左子树找到右子树的最左侧的节点（右子树中最小的位置），接上。

返回值设置为节点指针，外层需要接住，这样可以很方便地修改二叉树的结构

class Solution {
public:
    TreeNode* deleteNode(TreeNode* root, int key) {
        // 返回的节点通过外层接住
        // 终止条件就是所有的删除逻辑
        if (root == nullptr) return nullptr;
        if (root->val == key) {
            // 找到了
            if (!root->right && !root->left) {
                delete root;
                return nullptr;
            } else if (!root->right && root->left) {
                // 只有左边节点
                TreeNode* tmp = root->left;
                delete root;
                return tmp;
            } else if (!root->left && root->right) {
                // 只有右边节点
                TreeNode* tmp = root->right;
                delete root;
                return tmp;
            } else {
                // 右节点继承，左子树全移动到最左下方
                TreeNode* curr = root->right;
                while (curr->left) {
                    curr = curr->left;
                }
                curr->left = root->left;
                TreeNode* tmp = root->right;
                delete root;
                return tmp;
            }
        } 
        // 递归逻辑
        if (root->val < key) root->right = deleteNode(root->right, key);
        if (root->val > key) root->left = deleteNode(root->left, key);
        return root;
    }
};

4.7 修剪二叉搜索树

让节点中所有的数值保持在给定的区间内，同时不应该改变原有的树的结构

修建二叉树对结构需要重新修改，会稍微复杂一点

不可以在某个节点不符合条件时候直接删除并返回nullptr，因为其孩子是有可能符合区间条件的

注意：不需要在 LeetCode 中处理内存释放问题

正确逻辑：

1. 如果本节点小于下界，应该向右遍历（其右孩子是有可能符合条件的），大于同理
2. 如果符合条件，正常处理左右子树

class Solution {
public:
    TreeNode* trimBST(TreeNode* root, int low, int high) {

        if (!root) return nullptr;
        if (root->val < low) {
            // 从右子树继续递归，删除本节点
            return trimBST(root->right, low, high);
        } else if (root->val > high) {
            return trimBST(root->left, low, high);
        }
        root->right = trimBST(root->right, low, high);
        root->left = trimBST(root->left, low, high);
        return root;
    }
};

4.8 有序数组转换为二叉平衡搜索树

有一些点需要注意，思考一下

什么时候不需要将根节点传入作为参数？为什么本题不需要通过判断传入参数来 return nullptr

class Solution {
public:
    TreeNode* sortedArrayToBST(vector<int>& nums) {
        int left = 0;
        int right = nums.size();
        TreeNode* root = nullptr;
        root = _build(nums, left, right);
        return root;
    }    
    TreeNode* _build(vector<int>& nums, int left, int right) {
        // 组里面没有元素了
        if (left >= right) return nullptr;    
        int mid = ((right - left) / 2) + left;

        // 构建中点，外层接住
        TreeNode* curr = new TreeNode(nums[mid]);
        curr->left = _build(nums, left, mid);
        curr->right = _build(nums, mid + 1, right);

        return curr;
    }
};

5 易混淆点

5.1 节点指针参数

5.1.1 不需要传递节点指针

当每次递归都独立创建或遍历子树，父节点仅需接收返回值挂接：

TreeNode* build(const vector<int>& nums, int l, int r) {
    if (l >= r) return nullptr;
    int m = (l + r) / 2;
    TreeNode* root = new TreeNode(nums[m]);
    root->left = build(nums, l, m);
    root->right = build(nums, m + 1, r);
    return root;
}

每一层都独立产生节点，不依赖外层状态，不传当前节点指针。
这种结构用于：

• 构建树（如 sortedArrayToBST）
• 查找并返回新根（如 trimBST、invertTree）
• 需要改变结构并返回新子树时

5.1.2 需要传递节点指针

当函数要在原有节点基础上修改或统计信息，且操作依赖父层状态：

void dfs(TreeNode* node, int depth, int& sum) {
    if (!node) return;
    if (!node->left && !node->right) sum += depth;
    dfs(node->left, depth + 1, sum);
    dfs(node->right, depth + 1, sum);
}

典型用途：

• 访问或统计整棵树（遍历）
• 回溯时要恢复状态
• 需要知道父节点信息或方向（左/右）

5.2 递归返回值

• 不要返回值：搜索整棵⼆叉树且不用处理递归返回值
• 需要返回值：搜索整棵⼆叉树且需要处理递归返回值
• 必须有返回：遇到符合条件的路径了就要及时返回，例如搜索其中⼀条符合条件的路径

只需要搜索⼀条边

if (递归函数(root->left)) return ;
if (递归函数(root->right)) return ;

搜索整个树

left = 递归函数(root->left);  // 左
right = 递归函数(root->right); // 右
left与right的逻辑处理;         // 中 

5.2.1 返回 void

当递归只是访问、打印、统计、累积而不改变结构，这种函数只是向外输出或修改外部变量，不需要返回子树。

void preorder(TreeNode* node) { ... }
void dfs(TreeNode* node, int& sum) { ... }

5.2.2 返回 TreeNode*

父节点要拿到新的子树根进行挂接，递归会改变树结构（删除、修剪、构造）：

TreeNode* trimBST(TreeNode* root, int low, int high);
TreeNode* invertTree(TreeNode* root);
TreeNode* deleteNode(TreeNode* root, int key);

5.2.3 返回 bool

用于存在性判断 / 条件是否满足，当子树满足条件时应提前终止或者向上报告

• 一旦有一个分支返回 true，整棵递归可结束。
• 常用于“是否存在路径”、“是否对称”、“是否平衡”等问题。

bool hasPathSum(TreeNode* node, int sum, int target) {
    if (!node) return false;
    sum += node->val;
    if (!node->left && !node->right) return sum == target;
    return hasPathSum(node->left, sum, target) || 
           hasPathSum(node->right, sum, target);
}

5.2.4 返回其他类型

常用于值的累积 / 特征汇总，常用于求高度、节点数、直径、最大路径和等。

int maxDepth(TreeNode* node) {
    if (!node) return 0;
    int l = maxDepth(node->left);
    int r = maxDepth(node->right);
    return std::max(l, r) + 1;
}