二叉树解题技巧

1遍历方式

1.1前序遍历（中左右）

  • 递归法思路：
    • 确定递归函数的参数和返回值：节点和数组、返回void
    • 确定终止条件：节点为空
    • 确定单层递归逻辑：中左右顺序
  • 伪代码：
    1
    2
    3
    4
    5
    6
    void traversal(TreeNode* cur, vector<int>& vec)
    if (cur==null) return
    ******递归部分******
    vec.push_back(cur->val);    // 中
    traversal(cur->left, vec);  // 左
    traversal(cur->right, vec); // 右
  • 迭代法思路：
    • 利用栈，顺序是栈顶元素（中）弹出，再按右左的顺序入栈
  • 伪代码
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    vector<int> preorderTraversal(TreeNode* root) {
      stack<TreeNode*> st;
      vector<int> result;
      if (root == NULL) return result;
      ******迭代部分******
      st.push(root);
      while (!st.empty()) {
          TreeNode* node = st.top();   // 中
          st.pop();
          result.push_back(node->val);
          if (node->right) st.push(node->right);// 右（空节点不入栈）
          if (node->left) st.push(node->left);  // 左（空节点不入栈）
      }
      return result;
    }
  • 统一迭代法思路：将访问的节点放入栈中，把要处理的节点也放入栈中但是要做标记。标记就是要处理的节点放入栈之后，紧接着放入一个空指针作为标记
  • 伪代码：
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    vector<int> inorderTraversal(TreeNode* root) {
      vector<int> result;
      stack<TreeNode*> st;
      if (root != NULL) st.push(root);
      ******迭代部分******
      while (!st.empty()) {
          TreeNode* node = st.top();
          if (node != NULL) {
            st.pop(); // 将该节点弹出，避免重复操作，下面再将右中左节点添加到栈中
            if (node->right) st.push(node->right);  // 添加右节点（空节点不入栈）

            st.push(node);                          // 添加中节点
            st.push(NULL); // 中节点访问过，但是还没有处理，加入空节点做为标记。

            if (node->left) st.push(node->left);    // 添加左节点（空节点不入栈）
          } else { // 只有遇到空节点的时候，才将下一个节点放进结果集
              st.pop();           // 将空节点弹出
              node = st.top();    // 重新取出栈中元素
              st.pop();
              result.push_back(node->val); // 加入到结果集
            }
      }
      return result;
    }

1.2中序遍历

  • 递归法：同前序
  • 迭代法：只能用统一迭代法

1.3后续遍历

  • 递归法：同前序
  • 迭代法：同前序，变成中左右入栈，中右左出栈，reverse变成左右中

1.4层序遍历

  • 思路：利用队列遍历每一层节点，并把他们的左右节点入队
  • 伪代码
    1
    2
    3
    4
    5
    6
    7
    根节点入队
    while的终止条件：队列不为空
      记录队列大小size（实质上是这一层的节点个数）
      遍历当前层元素（循环size次）
        队列弹出元素
        将元素的值添加到结果
        将左右节点放入队列

翻转二叉树

  • 思路：递归遍历
  • 伪代码：
    1
    2
    3
    4
    前序遍历：
      处理中间节点：交换左右节点
      递归左节点
      递归右节点

对称二叉树

  • 思路：后序遍历，左右中
  • 伪代码：
    1
    2
    3
    4
    5
    递归函数参数：左右两个子树，返回bool
    终止条件：左右节点为空或不同
    单层递归逻辑：
    比较二叉树外侧：左节点的左节点，右节点的右节点
    比较二叉树内侧，左节点的右节点，右节点的左节点

二叉树最大深度

  • 思路：前序遍历，每迭代一次++

2属性

3修改与构造

4二叉搜索树属性

5公共祖先

6二叉搜索树修改与构造