二叉树

递归遍历

• 递归三部曲
  • 确定递归函数的 参数 与 返回值。
  • 确定终止条件。
  • 确定单层递归逻辑。
• 前中后序遍历
• 实现细节
  • C++语言实现时，传入vector作为存放结果容器，但是递归函数的参数忘记写成引用形式，导致都是拷贝形式传参。
  • 注意：可能是上述前中后3中遍历模板题目，但不是常规意义上的，如可能找右中左这样的中序遍历顺序。
  • 代码

    void traversal(TreeNode* root, vector<int>& ans)
    

统一迭代形式

使用栈的话，无法同时解决访问节点（遍历节点）和处理节点（将元素放进结果集）不一致的情况。
故将访问的节点放入栈中，把要处理的节点也放入栈中但是要做标记。

即 将要处理的节点放入栈之后，紧接着放入一个空指针作为标记。 这种方法也可以叫做标记法。

• 注意点
  由于 结合了栈，代码逻辑 和 具体遍历顺序相反。
• 前序模板

	vector<int> preorderTraversal(TreeNode* root) {vector<int> ans;if (!root)return ans;stack<TreeNode*> stk;stk.push(root);while (!stk.empty()) {TreeNode* p = stk.top();if (p != nullptr) {stk.pop();if (p->right)stk.push(p->right);if (p->left)stk.push(p->left);stk.push(p);stk.push(nullptr);}else {stk.pop();p = stk.top();stk.pop();ans.push_back(p->val);}}return ans;}

• 中序模板

    vector<int> inorderTraversal(TreeNode* root) {vector<int> ans;if (root == nullptr)return ans;stack<TreeNode*> stk;stk.push(root);while (!stk.empty()) {TreeNode* p = stk.top();//访问节点if (p != nullptr) {stk.pop();if (p->right)stk.push(p->right);stk.push(p);//添加标记stk.push(nullptr);if (p->left)stk.push(p->left);}else {//处理节点stk.pop();p = stk.top();stk.pop();ans.push_back(p->val);}}return ans;}

层序遍历

迭代形式——队列

• 模板

      vector<vector<int>> levelOrder(TreeNode* root) {vector<vector<int>> ans;if (root == nullptr)return ans;queue<TreeNode*> que;que.push(root);while (!que.empty()) {int size = que.size();vector<int> level;while (size > 0) {size--;TreeNode* p = que.front();que.pop();level.push_back(p->val);if (p->left != nullptr)que.push(p->left);if (p->right != nullptr)que.push(p->right);}ans.push_back(level);}return ans;}
  

• 层间操作

题型

删除普通二叉树目标节点

要遍历整棵树。
与下文中二叉搜索树的删除节点类似，调整结构，对目标节点分类。

• 代码（随想录）
  • 用交换值的操作来删除目标节点
    思想：将目标节点值 和 右子树的最左节点值交换，之后目标节点变为了该最左节点，这是第一次；继续递归遍历，一直遍历到该最左节点即目标节点，然后若是右孩子为空，直接返回左孩子，这是第二次操作目标节点，注意若是右孩子不空，则会继续交换，然后重复，直到右孩子为空，可以删除。

      TreeNode* deleteNode(TreeNode* root, int key) {if (root == nullptr) return root;if (root->val == key) {if (root->right == nullptr) { // 这里第二次操作目标值：最终删除的作用return root->left;}TreeNode *cur = root->right;while (cur->left) {cur = cur->left;}swap(root->val, cur->val); // 这里第一次操作目标值：交换目标值其右子树最左面节点。}root->left = deleteNode(root->left, key);root->right = deleteNode(root->right, key);return root;}
  

  • 参考二叉搜索树，用指针 断开、重连等直接操作。

两棵树比较

• 二叉树自身子树比较——对称性质
  • 要通过递归函数的返回值来判断两个子树的内侧节点和外侧节点是否对应相等。
    • 即一个树的遍历顺序是左右中，一个树的遍历顺序是右左中，二者同步进行遍历。
    • 都可理解为是后序遍历，尽管已经不是严格上在一个树上进行遍历的后序遍历。

  • 递归模板

    class Solution {
    public:bool isSymmetric(TreeNode* root) {if (!root)return true;return traversal(root->left, root->right);}bool traversal(TreeNode* r1, TreeNode* r2) {if (!r1 && !r2)return true;if ((!r1 && r2) || (r1 && !r2) || (r1->val != r2->val))return false;bool outside = traversal(r1->left, r2->right);bool inside = traversal(r1->right, r2->left);return outside && inside;}
    };
    

  • 迭代
    • 任意使用 队列、栈、数组等容器，依然是 子树1的内侧节点和子树2的内侧节点同时进入容器，相应外侧节点同时进入。
• 比较两棵树是否相同
  • 类似 对称性质比较，只是 是 两棵树的 左节点 同时进入 、两棵树的右节点同时进入。
• 两棵树同时操作
  • 递归
  • 迭代法中，一般一起操作两个树都是使用队列模拟类似层序遍历，同时处理两个树的节点，这种方式最好理解，如果用模拟递归的思路的话，要复杂一些。

深度、高度问题

• 定义
  • 二叉树节点的深度：指从根节点到该节点的最长简单路径边的条数或者节点数（取决于深度从0开始还是从1开始）
  • 二叉树节点的高度：指从该节点到叶子节点的最长简单路径边的条数后者节点数（取决于高度从0开始还是从1开始）
• 角度转移
  • 当前节点的高度：以当前节点为根节点求最大深度，可以用后序遍历。
• 方法
  • 递归
    • 前序遍历：求根节点高度。
    • 后序遍历：求当前节点深度。
  • 迭代
    • 层序遍历：适合求当前节点的深度。
• 代码模板

    // 递归-后序遍历：求最小深度int traversal(TreeNode* root) {if (!root)return 0;int leftDpeth = traversal(root->left);int rightDpeth = traversal(root->right);if (root->left && !root->right)return 1 + leftDpeth;if (!root->left && root->right)return 1 + rightDpeth;return 1 + min(leftDpeth, rightDpeth);}// 递归-后序遍历：求最大深度int getdepth(treenode* node) {if (node == NULL) return 0;int leftdepth = getdepth(node->left);       // 左int rightdepth = getdepth(node->right);     // 右int depth = 1 + max(leftdepth, rightdepth); // 中return depth;}

完全二叉树

判断完全二叉树

• DFS
  后序遍历，一直向左递归的深度 == 一直向右递归的深度

        TreeNode* left = root->left, * right = root->right;int leftDepth = 0, rightDepth = 0;while (left) {left = left->left;leftDepth++;}while (right) {right = right->right;rightDepth++;}if (leftDepth == rightDepth)return (2 << leftDepth) - 1;// 注意(2<<1) 相当于2^2，所以leftDepth初始为0

• BFS
  层序遍历，结合 层数 和 当前层节点 之间的次幂关系。

        while (!que.empty()) {level++;int levelSize = que.size();ans += levelSize;int levelMaxSize = int(pow(2, level - 1));if (levelSize != levelMaxSize) {ans = levelMaxSize - 1 + levelSize;break;}

平衡二叉树

• 概念
  任意节点的左右子树的高度差值 不超过1.

• 深度 和 高度

  • 深度：指从根节点到该节点的最长简单路径边的条数。
  • 高度：指从该节点到叶子节点的最长简单路径边的条数。

• 代码

  • 递归——后序遍历（比较高度）
    • 参数，返回值
      • 返回值：0表示当前节点的左右子树高度相等；-1表示当前节点的左右子树已经违反平衡二叉树的规则，直接中断判断；x表示当前节点的高度。
    • 代码

    int getHeight(TreeNode* root) {int leftHeight = getHeight(node->left); // 左if (leftHeight == -1) return -1;int rightHeight = getHeight(node->right); // 右if (rightHeight == -1) return -1;int result;if (abs(leftHeight - rightHeight) > 1) {  // 中result = -1;} else {result = 1 + max(leftHeight, rightHeight); // 以当前节点为根节点的树的最大高度}return result;
    }
    

  • 迭代——后序遍历的迭代形式
    • 以当前节点为根节点，求其子树的最大深度 即该节点的高度。

左叶子

• 当前节点的左孩子是否为叶子。
• 反常规，通过父节点判断 左孩子，而非常规通过孩子判断父节点。

最大树

• 类似用数组构造二叉树的题目，每次分隔尽量不要定义新的数组，而是通过下标索引直接在原数组上操作，这样可以节约时间和空间上的开销。
  • 在递归时可用 索引限制每次递归处理的范围，如[begin, end)。
• 不同代码风格的实现，一般情况来说：如果让空节点（空指针）进入递归，就不加if，如果不让空节点进入递归，就加if限制一下， 终止条件也会相应的调整。
  • 允许空节点进入，则会代码简洁一些。

二叉搜索树

• 关键点
  中序遍历

• 一种常见手法
  中序遍历时的pre指针

• 节点有序

  • 在二叉树上进行二分查找。

• 查找

  • 递归
    • 由于节点有序性，不需要回溯。

• 验证二叉搜索树

  • 借助中序遍历，使用一个pre指针，次一点则是借助数组存储中序结果。
  • 代码

      // 下列 pre指针是 引用类型bool traversal(TreeNode* root, TreeNode* & pre) {if (!root)return true;bool left = traversal(root->left, pre);if (pre && pre->val >= root->val)return false;            pre = root;bool right = traversal(root->right, pre);return left && right;}
  

• 二叉搜索树插入节点
  正常遍历，然后插入在叶子节点即可，无需涉及结构调整。

• 二叉搜索树删除节点
  需要涉及到 结构调整。

  • 递归函数返回值问题
    因为涉及到结构调整，所以下层操作完后，回溯后，需要更新结构，对父节点的孩子节点重新设置。
    相当于把新的节点返回给上一层，上一层就要用 root->left 或者 root->right接住。
  • 目标节点 进行分类：
    • 目标节点为叶子节点，直接删除。
    • 目标节点有一边为空，则用非空的孩子顶替 目标节点位置。
    • 目标节点同时有左右孩子，将左孩子放在右孩子树的最左节点的左孩子位置。
  • 代码（随想录）

    TreeNode* deleteNode(TreeNode* root, int key) {if (root == nullptr) return root; // 第一种情况：没找到删除的节点，遍历到空节点直接返回了if (root->val == key) {// 第二种情况：左右孩子都为空（叶子节点），直接删除节点， 返回NULL为根节点if (root->left == nullptr && root->right == nullptr) {///! 内存释放delete root;return nullptr;}// 第三种情况：其左孩子为空，右孩子不为空，删除节点，右孩子补位 ，返回右孩子为根节点else if (root->left == nullptr) {auto retNode = root->right;///! 内存释放delete root;return retNode;}// 第四种情况：其右孩子为空，左孩子不为空，删除节点，左孩子补位，返回左孩子为根节点else if (root->right == nullptr) {auto retNode = root->left;///! 内存释放delete root;return retNode;}// 第五种情况：左右孩子节点都不为空，则将删除节点的左子树放到删除节点的右子树的最左面节点的左孩子的位置// 并返回删除节点右孩子为新的根节点。else {TreeNode* cur = root->right; // 找右子树最左面的节点while(cur->left != nullptr) {cur = cur->left;}cur->left = root->left; // 把要删除的节点（root）左子树放在cur的左孩子的位置TreeNode* tmp = root;   // 把root节点保存一下，下面来删除root = root->right;     // 返回旧root的右孩子作为新rootdelete tmp;             // 释放节点内存（这里不写也可以，但C++最好手动释放一下吧）return root;}}//更新 结构if (root->val > key) root->left = deleteNode(root->left, key);if (root->val < key) root->right = deleteNode(root->right, key);return root;
    }
    

最近公共祖先

• 需求
  自底向上搜索，查看公共祖先，故用到回溯过程，即 后序遍历。
• 回溯过程中的返回值问题

  • 在回溯的过程中，必然要遍历整棵二叉树[重点]，即使已经找到结果了，依然要把其他节点遍历完，因为要使用递归函数的返回值（也就是代码中的left和right）做逻辑判断。

  • 要理解如果返回值left为空，right不为空为什么要返回right，为什么可以用返回right传给上一层结果。

  • 本题就是标准的搜索整棵树的写法，遇到递归函数的返回值，需要对返回值进行处理，模板如下：

    • 搜索一条边

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

  • 搜索整棵树

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

  • 返回值，一般也可以建立父节点和子节点之间的关系。