二叉树力扣经典题型与特殊解法

Category： DSA

写在前面

一些基本关系

结点数和树高

\[hh\]

完全二叉树节点范围

节点定义

取自 LeetCode.

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

遍历

这里有四种, 分别是层序(BFS)和前中后序(DFS), 给出递归和迭代实现, 当然还有一种比较骚的Morris遍历, 这里就仅供欣赏了.

迭代法采用统一写法(插入空节点标记根节点法), 好记!

前序

144. 二叉树的前序遍历;

class Solution {
public:
    vector<int> preorderTraversal(TreeNode* root) {
        vector<int> ans{};
        function<void(TreeNode*)> f = [&](TreeNode* node) {
            if (!node) return;
            ans.emplace_back(node->val);
            f(node->left);
            f(node->right);
        };
        f(root);
        return ans;
    }
};

迭代:

class Solution {
public:
    vector<int> preorderTraversal(TreeNode* root) {
        if (!root) return {};
        vector<int> ans{};
        stack<TreeNode*> st;
        if (root) st.emplace(root);
        while (!st.empty()) {
            auto node = st.top();
            st.pop();
            if (node) { // 只修改这里的顺序
                if (node->right) st.emplace(node->right);
                if (node->left) st.emplace(node->left);
                st.emplace(node);
                st.emplace(nullptr);
            } else {
                node = st.top(), st.pop();
                ans.emplace_back(node->val);
            }
        }
        return ans;
    }
};

Morris:

class Solution {
public:
    vector<int> preorderTraversal(TreeNode* root) {
        if (!root) return {};
        vector<int> ans{};
        TreeNode *cur = root, *pre = nullptr;
        while (cur) {
            if (!cur->left) {
                ans.push_back(cur->val);
                cur = cur->right;
            } else {
                // 定位左子树
                pre = cur->left;
                // 找左子树的最右节点(不能与cur相同)
                while (pre->right && pre->right != cur) pre = pre->right;
                if (!pre->right) {
                    pre->right = cur;
                    ans.push_back(cur->val);
                    cur = cur->left;
                } else {
                    pre->right = nullptr;
                    cur = cur->right;
                }
            }
        }
        return ans;
    }
};

中序

94. 二叉树的中序遍历;

class Solution {
public:
    vector<int> inorderTraversal(TreeNode* root) {
        vector<int> ans{};
        function<void(TreeNode*)> f = [&](TreeNode* node) {
            if (!node) return;
            f(node->left);
            ans.emplace_back(node->val);
            f(node->right);
        };
        f(root);
        return ans;
    }
};

迭代:

class Solution {
public:
    vector<int> inorderTraversal(TreeNode* root) {
        vector<int> ans{};
        stack<TreeNode*> st;
        if (root) st.emplace(root);
        while (!st.empty()) {
            auto node = st.top();
            st.pop();
            if (node) {
                if (node->right) st.emplace(node->right);
                st.emplace(node);
                st.emplace(nullptr);
                if (node->left) st.emplace(node->left);
            } else {
                node = st.top(), st.pop();
                ans.emplace_back(node->val);
            }
        }
        return ans;
    }
};

Morris:

class Solution {
public:
    vector<int> inorderTraversal(TreeNode* root) {
        vector<int> ans{};
        TreeNode *cur = root, *pre = nullptr;
        while (cur) {
            if (!cur->left) {
                ans.push_back(cur->val);
                cur = cur->right;
            } else {
                pre = cur->left;
                while (pre->right && pre->right != cur) pre = pre->right;
                if (!pre->right) {
                    pre->right = cur;
                    cur = cur->left;
                } else {
                    pre->right = nullptr;
                    ans.push_back(cur->val);
                    cur = cur->right;
                }
            }
        }
        return ans;
    }
};

后序

145. 二叉树的后序遍历;

class Solution {
public:
    vector<int> postorderTraversal(TreeNode* root) {
        vector<int> ans{};
        function<void(TreeNode*)> f = [&](TreeNode* node) {
            if (!node) return;
            f(node->left);
            f(node->right);
            ans.emplace_back(node->val);
        };
        f(root);
        return ans;
    }
};

迭代:

class Solution {
public:
    vector<int> postorderTraversal(TreeNode* root) {
        vector<int> ans{};
        stack<TreeNode*> st;
        if (root) st.emplace(root);
        while (!st.empty()) {
            auto node = st.top();
            st.pop();
            if (node) {
                st.emplace(node);
                st.emplace(nullptr);
                if (node->right) st.emplace(node->right);
                if (node->left) st.emplace(node->left);
            } else {
                node = st.top(), st.pop();
                ans.emplace_back(node->val);
            }
        }
        return ans;
    }
};

Morris:

class Solution {
public:
    vector<int> postorderTraversal(TreeNode* root) {
        vector<int> ans{};
        auto addPath = [&](TreeNode* node) {
            // addPath 添加至结果数组, 然后完成部分数组反转
            int count{};
            while (node) {
                ++count;
                ans.emplace_back(node->val);
                node = node->right;
            }
            reverse(ans.end() - count, ans.end());
        };
        TreeNode *cur = root, *pre = nullptr;
        while (cur) {
            pre = cur->left;
            if (!pre)
                cur = cur->right;
            else {
                while (pre->right && pre->right != cur) pre = pre->right;
                if (!pre->right) {
                    pre->right = cur;
                    cur = cur->left;
                } else {
                    pre->right = nullptr;
                    addPath(cur->left);
                    cur = cur->right;
                }
            }
        }
        addPath(root);
        return ans;
    }
};

层序

102. 二叉树的层序遍历;

class Solution {
public:
    vector<vector<int>> levelOrder(TreeNode* root) {
        queue<TreeNode*> que;
        if (root) que.emplace(root);
        vector<vector<int>> ans;
        vector<int> path;
        while (!que.empty()) {
            path.clear();
            int qsize = que.size();
            for (int i{}; i < qsize; ++i) {
                auto node = que.front();
                que.pop();
                path.emplace_back(node->val);
                if (node->left) que.emplace(node->left);
                if (node->right) que.emplace(node->right);
            }
            ans.emplace_back(path);
        }
        return ans;
    }
};

107. 二叉树的层序遍历 II;

class Solution {
public:
    vector<vector<int>> levelOrderBottom(TreeNode* root) {
        queue<TreeNode*> que;
        if (root) que.emplace(root);
        vector<vector<int>> ans;
        vector<int> path;
        while (!que.empty()) {
            path.clear();
            int qsize = que.size();
            for (int i{}; i < qsize; ++i) {
                auto node = que.front();
                que.pop();
                path.emplace_back(node->val);
                if (node->left) que.emplace(node->left);
                if (node->right) que.emplace(node->right);
            }
            ans.emplace_back(path);
        }
        reverse(ans.begin(), ans.end());
        return ans;
    }
};

层序遍历的变体

103. 二叉树的锯齿形层序遍历;

class Solution {
public:
    vector<vector<int>> zigzagLevelOrder(TreeNode* root) {
        queue<TreeNode*> que;
        if (root) que.emplace(root);
        vector<vector<int>> ans;
        vector<int> path;
        int k{};
        while (!que.empty()) {
            path.clear();
            int qsize = que.size();
            for (int i{}; i < qsize; ++i) {
                auto node = que.front();
                que.pop();
                path.emplace_back(node->val);
                if (node->left) que.emplace(node->left);
                if (node->right) que.emplace(node->right);
            }
            if (k++ & 1) reverse(path.begin(), path.end());
            ans.emplace_back(path);
        }
        return ans;
    }
};

恢复(构建)二叉树

前序和后序

889. 根据前序和后序遍历构造二叉树;

class Solution {
public:
    TreeNode* constructFromPrePost(vector<int>& preorder,
                                   vector<int>& postorder) {
        if (preorder.empty() || postorder.empty()) return nullptr;
        int n = preorder.size(); // 左闭右开区间
        function<TreeNode*(int, int, int, int)> f = [&](int prL, int prR,
                                                        int poL, int poR) {
            if (prL == prR || poL == poR)
                return static_cast<TreeNode*>(nullptr);
            auto root = new TreeNode(preorder[prL]);
            // 剪枝, 这步必须加, 因为当前根节点的下一个节点可能会溢出
            if (prR - 1 == prL) return root;
            int i{poL}; // i表示前序根节点的下一个节点在后序中的位置
            while (postorder[i] != preorder[prL + 1]) ++i;
            // l-tree: i - poL + 1
            root->left = f(prL + 1, prL + 2 + i - poL, poL, i + 1);
            root->right = f(prL + 2 + i - poL, prR, i + 1, poR - 1);
            return root;
        };
        return f(0, n, 0, n);
    }
};

前序和中序

105. 从前序与中序遍历序列构造二叉树;剑指 Offer 07. 重建二叉树;

class Solution {
public:
    TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
        if (preorder.empty() || inorder.empty()) return nullptr;
        int n = preorder.size(); // 左闭右开区间
        function<TreeNode*(int, int, int, int)> f = [&](int pl, int pr, int il,
                                                        int ir) {
            if (pl == pr || il == ir) return static_cast<TreeNode*>(nullptr);
            int rootVal{preorder[pl]};
            auto root = new TreeNode(rootVal);
            // if (pr - 1 == pl) return root; // 剪枝
            int i{il};
            while (inorder[i] != rootVal) ++i;              // find root idx
            root->left = f(pl + 1, pl + 1 + i - il, il, i); // l-tree: i-il
            root->right = f(pl + 1 + i - il, pr, i + 1, ir);
            return root;
        };
        return f(0, n, 0, n);
    }
};

中序和后序

106. 从中序与后序遍历序列构造二叉树;

class Solution {
public:
    TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) {
        if (inorder.empty() || postorder.empty()) return nullptr;
        int n = inorder.size();
        function<TreeNode*(int, int, int, int)> f = [&](int il, int ir, int pl,
                                                        int pr) {
            if (il == ir || pl == pr) return static_cast<TreeNode*>(nullptr);
            int rootVal{postorder[pr - 1]};
            auto root = new TreeNode(rootVal);
            if (pr - 1 == pl) return root;
            int i{il};
            while (inorder[i] != rootVal) ++i;
            root->left = f(il, i, pl, pl + i - il); // 左子树结点数: i - il
            root->right = f(i + 1, ir, pl + i - il, pr - 1);
            return root;
        };
        return f(0, n, 0, n);
    }
};

序列化和反序列化

297. 二叉树的序列化与反序列化;

class Codec {
public:
    string serialize(TreeNode* root) {
        string s;
        function<void(TreeNode*)> f = [&](TreeNode* node) {
            if (!node) {
                s += "#,";
                return;
            }
            s += to_string(node->val) + ",";
            f(node->left);
            f(node->right);
        };
        f(root);
        return s;
    }

    TreeNode* deserialize(string data) {
        list<string> ls{};
        string tmp;
        for (char c : data)
            if (c == ',')
                ls.emplace_back(tmp), tmp.clear();
            else
                tmp += c;
        function<TreeNode*()> f = [&]() {
            if (ls.front() == "#"s) {
                ls.erase(ls.begin());
                return static_cast<TreeNode*>(nullptr);
            }
            auto root = new TreeNode(stoi(ls.front()));
            ls.erase(ls.begin());
            root->left = f();
            root->right = f();
            return root;
        };
        return f();
    }
};

评论区看到的好方法(用C++的stringstream)

class Codec {
public:
    string serialize(TreeNode* root) {
        if (!root) return "#"s;
        return to_string(root->val) + " " + serialize(root->left) + " " +
               serialize(root->right);
    }

    TreeNode* deserialize(string data) {
        istringstream ss(data);
        function<TreeNode*()> f = [&]() {
            string tmp;
            ss >> tmp;
            if (tmp == "#"s) return static_cast<TreeNode*>(nullptr);
            return new TreeNode(stoi(tmp), f(), f());
        };
        return f();
    }
};

构建最大的二叉树

654. 最大二叉树;

递归直接找最大值构建即可:

class Solution {
public:
    TreeNode* constructMaximumBinaryTree(vector<int>& nums) {
        function<TreeNode*(int, int)> f = [&](int l, int r) {
            if (l >= r) return (TreeNode*)nullptr;
            auto idx =
                max_element(nums.begin() + l, nums.begin() + r) - nums.begin();
            return new TreeNode(nums[idx], f(l, idx), f(idx + 1, r));
        };
        return f(0, nums.size());
    }
};

迭代需要单调栈模拟, 不太好想:

class Solution {
public:
    TreeNode* constructMaximumBinaryTree(vector<int>& nums) {
        int n = nums.size();
        vector<int> st;
        vector<TreeNode*> tree(n);
        for (int i = 0; i < n; ++i) {
            tree[i] = new TreeNode(nums[i]);
            while (!st.empty() && nums[i] > nums[st.back()]) {
                tree[i]->left = tree[st.back()];
                st.pop_back();
            }
            if (!st.empty()) tree[st.back()]->right = tree[i];
            st.push_back(i);
        }
        return tree[st[0]];
    }
};

性质(属性)

对称

101. 对称二叉树; 剑指 Offer 28. 对称的二叉树;

class Solution {
public:
    bool isSymmetric(TreeNode* root) {
        if (!root) return true;
        function<bool(TreeNode*, TreeNode*)> f = [&](TreeNode* p, TreeNode* q) {
            if (!p && !q) return true;
            if (!p || !q || p->val != q->val) return false;
            return f(p->left, q->right) && f(p->right, q->left);
        };
        return f(root->right, root->left);
    }
};

BFS:

class Solution {
public:
    bool isSymmetric(TreeNode* root) {
        if (!root) return true;
        queue<TreeNode*> q;
        q.emplace(root), q.emplace(root);
        while (!q.empty()) {
            auto u = q.front();
            q.pop();
            auto v = q.front();
            q.pop();
            if (!u && !v) continue; // 未到达叶结点, 不能像递归那样直接返回 true
            if (!u || !v || u->val != v->val) return false;
            q.emplace(u->right), q.emplace(v->left);
            q.emplace(u->left), q.emplace(v->right);
        }
        return true;
    }
};

平衡

110. 平衡二叉树;

class Solution {
public:
    bool isBalanced(TreeNode* root) {
        if (!root) return true;
        function<int(TreeNode*)> f = [&](TreeNode* node) {
            if (!node) return 0;
            int l = f(node->left);
            if (l == -1) return -1;
            int r = f(node->right);
            if (r == -1) return -1;
            return abs(l - r) > 1 ? -1 : 1 + max(l, r);
        };
        return ~f(root);
    }
};

迭代:

子树

剑指 Offer 26. 树的子结构;

子结构, 即 B 到了空即可, A 此时可能还有值.

class Solution {
public:
    bool f(TreeNode* A, TreeNode* B) {
        if (!B) return true; // B空说明比较完毕
        if (!A) return false;
        return A->val == B->val && f(A->left, B->left) && f(A->right, B->right);
    }
    bool isSubStructure(TreeNode* A, TreeNode* B) {
        if (!B || !A) return false;
        return f(A, B) || isSubStructure(A->left, B) ||
               isSubStructure(A->right, B);
    }
};

面试题 04.10. 检查子树;(和上面不太一样, 必须完全是子树, 不能仅有一部分相同)

完全是子树, 即判断函数(f())中两个节点都遍历到空节点为止.

class Solution {
public: // 必须遍历到都为空才为 true
    bool f(TreeNode* t1, TreeNode* t2) {
        if (!t2 && !t1) return true;
        if (!t2 || !t1) return false;
        return t1->val == t2->val && f(t1->left, t2->left) &&
               f(t1->right, t2->right);
    }
    bool checkSubTree(TreeNode* t1, TreeNode* t2) {
        if (!t2 && !t1) return true;
        if (!t1) return false;
        return f(t1, t2) || checkSubTree(t1->left, t2) ||
               checkSubTree(t1->right, t2);
    }
};

宽度

是基于下面这个事实:

二叉树的当前节点编号为$i$, 则其左子结点和右子节点的编号分别为$2 i$和$2i+1$.

其中的结点编号都是连续的正整数. 是不是有点像二叉堆(优先队列)的标号呢?

有了上面的结论, 我们很容易得到下面几道题的思路, 就是在层序遍历中计算节点编号即可.

但是这里要注意, 上面的编号是针对满二叉树来说的, 也就是说, 如果有空节点也要相应编号, 否则就会乱套.

655. 输出二叉树 - 力扣（LeetCode）;

了解BFS 之后就很简单了.

class Solution {
public:
    vector<vector<string>> printTree(TreeNode* root) {
        if (!root) return vector<vector<string>>{};
        function<int(TreeNode*)> f = [&](TreeNode* node) {
            if (!node) return 0;
            return max(f(node->left), f(node->right)) + 1;
        };
        int m = f(root), n = (1 << m) - 1;
        vector<vector<string>> ans(m, vector<string>(n));
        queue<pair<TreeNode*, int>> q;
        q.emplace(root, (n - 1) >> 1);
        int r{};
        while (!q.empty()) {
            int n = q.size();
            while (n--) {
                auto [node, c] = q.front();
                q.pop();
                ans[r][c] = to_string(node->val);
                if (node->left) q.emplace(node->left, c - (1 << (m - r - 2)));
                if (node->right) q.emplace(node->right, c + (1 << (m - r - 2)));
            }
            ++r;
        }
        return ans;
    }
};

深搜看起来没那么直观:

class Solution {
public:
    vector<vector<string>> printTree(TreeNode* root) {
        if (!root) return vector<vector<string>>{};
        function<int(TreeNode*)> f = [&](TreeNode* node) {
            if (!node) return 0;
            return max(f(node->left), f(node->right)) + 1;
        };
        int m = f(root), n = (1 << m) - 1;
        vector<vector<string>> ans(m, vector<string>(n));
        function<void(TreeNode*, int, int)> g = [&](TreeNode* node, int r,
                                                    int c) {
            ans[r][c] = to_string(node->val);
            if (node->left) g(node->left, r + 1, c - (1 << (m - r - 2)));
            if (node->right) g(node->right, r + 1, c + (1 << (m - r - 2)));
        };
        g(root, 0, (n - 1) >> 1);
        return ans;
    }
};

662. 二叉树最大宽度 - 力扣（LeetCode）;(算是655的进阶版, 需要自己计算编号, 相减得出宽度, ull 实在是恶心到了)

class Solution {
public:
    int widthOfBinaryTree(TreeNode* root) {
        if (!root) return 0;
        using ll = unsigned long long;
        queue<pair<TreeNode*, ll>> q{{pair{root, 0}}};
        ll ans{};
        while (!q.empty()) {
            ll num{}, l{};
            for (int i{}, nq = q.size(); i < nq; ++i) {
                auto node = q.front().first;
                num = q.front().second;
                if (!l) l = num;
                q.pop();
                if (node->left) q.emplace(node->left, (num << 1) + 1);
                if (node->right) q.emplace(node->right, (num + 1) << 1);
            }
            ans = max(ans, num - l + 1);
        }
        return ans;
    }
};

深度(树高)

剑指 Offer 55 - I. 二叉树的深度;104. 二叉树的最大深度; ```cpp class Solution { public: int maxDepth(TreeNode* root) { if (!root) return 0; return max(maxDepth(root->left), maxDepth(root->right)) + 1; } };

 // BFS
 class Solution {
 public:
     int maxDepth(TreeNode* root) {
         if (!root) return 0;
         int ans{};
         queue<TreeNode*> q;
         q.emplace(root);
         while (!q.empty()) {
             int n = q.size();
             while (n--) {
                 auto node = q.front();
                 q.pop();
                 if (node->left) q.emplace(node->left);
                 if (node->right) q.emplace(node->right);
             }
             ++ans;
         }
         return ans;
     }
 };
 ```

111. 二叉树的最小深度; (这种题感觉还是 BFS 快, 因为不会遍历全部子树)

 ```cpp
 // DFS
 public:
     int minDepth(TreeNode* root) {
         if (!root) return 0;
         if (!root->left && !root->right) return 1;
         int ans{INT_MAX};
         if (root->left) ans = min(ans, minDepth(root->left));
         if (root->right) ans = min(ans, minDepth(root->right));
         return ans + 1;
     }
 };
 
 
 // BFS
 class Solution {
 public:
     int minDepth(TreeNode* root) {
         if (!root) return 0;
         queue<TreeNode*> q;
         q.emplace(root);
         int ans{1};
         while (!q.empty()) {
             int n = q.size();
             while (n--) {
                 auto node = q.front();
                 q.pop();
                 // 贪心, 遇到叶结点 就是最小的
                 if (!node->left && !node->right) return ans;
                 if (node->left) q.emplace(node->left);
                 if (node->right) q.emplace(node->right);
             }
             ++ans;
         }
         return ans;
     }
 };
 ```

结点数

222. 完全二叉树的节点个数;

路径

257. 二叉树的所有路径; 我的思路: 回溯, 注意更新答案时候, 不放入最后一个元素(vs), 这样可以方便回溯计算长度

  ```cpp
  class Solution {
  public:
      vector<string> binaryTreePaths(TreeNode* root) {
          string path{};
          vector<string> ans{};
          function<void(TreeNode*)> f = [&](TreeNode* node) {
              if (!node) return;
              auto vs = to_string(node->val);
              if (!node->left && !node->right)
                  ans.emplace_back(path + vs);
              else {
                  path += vs + "->"s;
                  f(node->left);
                  f(node->right);
                  path = std::move(path.substr(0, path.size() - 2 - vs.size()));
              }
          };
          f(root);
          return ans;
      }
  };
  // 官方
  class Solution {
  public:
      vector<string> binaryTreePaths(TreeNode* root) {
          vector<string> ans{};
          function<void(TreeNode*, string)> f = [&](TreeNode* node, string path) {
              if (!node) return;
              path += to_string(node->val);
              if (!node->left && !node->right) {
                  ans.emplace_back(path);
              } else {
                  path += "->"s;
                  f(node->left, path);
                  f(node->right, path);
              }
          };
          f(root, ""s);
          return ans;
      }
  };
  ```

二叉树的直径

543. 二叉树的直径;

class Solution {
public:
    int diameterOfBinaryTree(TreeNode *root) {
        int ans{};
        function<int(TreeNode *)> f = [&](TreeNode *node) {
            if (!node) return 0;
            int l = f(node->left), r = f(node->right);
            ans = max(ans, l + r);
            return max(l, r) + 1;
        };
        f(root);
        return ans;
    }
};

迭代法:

class Solution {
public:
    int diameterOfBinaryTree(TreeNode* root) {
        if (!root) return 0;

        int ans = 0;
        unordered_map<TreeNode*, int> depths{{nullptr, -1}};
        stack<TreeNode*> stk{{root}};

        while (!stk.empty()) {
            TreeNode* node = stk.top();
            if (depths.count(node->left) == 0) {
                stk.push(node->left);
            } else if (depths.count(node->right) == 0) {
                stk.push(node->right);
            } else {
                stk.pop();
                int l_len = depths[node->left] + 1;
                int r_len = depths[node->right] + 1;
                ans = max(ans, l_len + r_len);
                depths[node] = max(l_len, r_len);
            }
        }
        return ans;
    }
};

最大路径和

124. 二叉树中的最大路径和;

class Solution {
public:
    int maxPathSum(TreeNode* root) {
        int ans{INT_MIN};
        function<int(TreeNode*)> f = [&](TreeNode* node) {
            if (!node) return 0;
            int l{f(node->left)};
            int r{f(node->right)};
            ans = max(ans, l + r + node->val);
            return max(max(l, r) + node->val, 0);
        };
        f(root);
        return ans;
    }
};

祖先

这部分性质比较难, 因为需要是一些 ACM 的题目, 参考了0x3f的模板.

1483. 树节点的第 K 个祖先;

操作

这里主要是指对一般二叉树的操作.

翻转

226. 翻转二叉树;剑指 Offer 27. 二叉树的镜像;

class Solution {
public:
    TreeNode* invertTree(TreeNode* root) {
        queue<TreeNode*> que;
        if (root) que.emplace(root);
        while (!que.empty()) {
            auto node = que.front();
            que.pop();
            swap(node->left, node->right); // 库函数
            if (node->left) que.emplace(node->left);
            if (node->right) que.emplace(node->right);
        }
        return root;
    }
};

递归(DFS):

class Solution {
public:
    TreeNode* invertTree(TreeNode* root) {
        if (!root) return root;
        auto l = invertTree(root->right), r = invertTree(root->left);
        root->left = l;
        root->right = r;
        return root;
    }
};

迭代DFS: (栈模拟)

class Solution {
public:
    TreeNode* mirrorTree(TreeNode* root) {
        stack<TreeNode*> st;
        if (root) st.emplace(root);
        while (!st.empty()) {
                auto cur = st.top();
                swap(cur->left, cur->right); // 操作
                st.pop();
                if (cur->left) st.emplace(cur->left);
                if (cur->right) st.emplace(cur->right);
        }
        return root;
    }
};

合并

617. 合并二叉树;

class Solution {
public:
    TreeNode* mergeTrees(TreeNode* root1, TreeNode* root2) {
        if (!root1) return root2;
        if (!root2) return root1;
        root1->val += root2->val;
        root1->left = mergeTrees(root1->left, root2->left);
        root1->right = mergeTrees(root1->right, root2->right);
        return root1;
    }
};

删除特定节点

不太好想, 遍历时候需要存储当前节点, 也即递归函数返回值不是 void, 删点成林需要后序遍历, 最后讨论根节点.

1080. 根到叶路径上的不足节点;

1110. 删点成林;(经典的后序遍历应用)

class Solution {
public:
    vector<TreeNode*> delNodes(TreeNode* root, vector<int>& to_delete) {
        if (!root) return {};
        vector<TreeNode*> ans;
        unordered_set<int> st(to_delete.begin(), to_delete.end());
        function<TreeNode*(TreeNode*)> f = [&](TreeNode* node) {
            if (!node) return node;
            node->left = f(node->left);
            node->right = f(node->right);
            if (!st.count(node->val)) return node;
            if (node->left) ans.emplace_back(node->left);
            if (node->right) ans.emplace_back(node->right);
            delete node;
            return (TreeNode*)nullptr;
        };
        if (f(root)) ans.emplace_back(root);
        return ans;
    }
};

二叉搜索树

二叉搜索树是满足下面性质的一类特殊的二叉树:

若任意节点的左子树不空，则左子树上所有节点的值均小于它的根节点的值；
若任意节点的右子树不空，则右子树上所有节点的值均大于它的根节点的值；
任意节点的左、右子树也分别为二叉搜索树；

一个例子: (Wikipedia)

           8
         /   \
        3     10
       / \      \
      1   6      14
         / \     /
        4   7   13

有时候也可以不严格定义, 使二叉搜索树存在重复值节点.

验证

98. 验证二叉搜索树;(有四样写法)

中序遍历: (最好理解, 很直观, 存一下 pre 节点即可)

可以说一看到二叉搜索树就要想到中序遍历, 就像有序+最大最小要想到二分一样

class Solution {
public:
    TreeNode* pre{};
    bool isValidBST(TreeNode* root) {
        if (!root) return true;
        bool l = isValidBST(root->left);
        if (pre && pre->val >= root->val) return false;
        pre = root;
        bool r = isValidBST(root->right);
        return l && r;
    }
};
// 迭代也可以做: (复习一下中序遍历迭代法
class Solution {
public:
    bool isValidBST(TreeNode* root) {
        if (!root) return true;
        stack<TreeNode*> st;
        TreeNode* pre{};
        while (!st.empty() || root) {
            if (root) {
                st.emplace(root);
                root = root->left;
            } else {
                root = st.top();
                st.pop();
                if (pre && pre->val >= root->val) return false;
                pre = root;
                root = root->right;
            }
        }
        return true;
    }
};

前序遍历, 参考0x3f 题解, 代码非常丝滑, 注意这里由于数据范围是[INT_MIN,INT_MAX], 所以边界值要用LONG_MIN 和LONG_MAX

class Solution {
public:
    bool isValidBST(TreeNode* root, long l=LONG_MIN, long r=LONG_MAX) {
        if (!root) return true;
        auto x=root->val;
        return l<x&&x < r && isValidBST(root->left, l, x)&&isValidBST(root->right, x, r);
    }
};

后序遍历: (树上 DP 的基础, 慢慢研究)

class Solution {
public:
    bool isValidBST(TreeNode* root) {
        function<pair<long, long>(TreeNode*)> f = [&](TreeNode* node) {
            if (!node) return pair{LONG_MAX, LONG_MIN};
            auto [lmn, lmx] = f(node->left);
            auto [rmn, rmx] = f(node->right);
            long x = node->val;
            if (x <= lmx || x >= rmn) return pair{LONG_MIN, LONG_MAX};
            return pair{min(lmn, x), max(rmx, x)};
        };
        return f(root).second != LONG_MAX;
    }
};

搜索

700. 二叉搜索树中的搜索;

递归:

class Solution {
public:
    TreeNode* searchBST(TreeNode* root, int val) {
        if (!root) return nullptr;
        if (root->val == val) return root;
        if (root->val > val) root = searchBST(root->left, val);
        else root = searchBST(root->right, val);
        return root;
    }
};

迭代: (二叉树中最好写的迭代法了)

class Solution {
public:
    TreeNode* searchBST(TreeNode* root, int val) {
        while (root) {
            if (!root) return nullptr;
            if (root->val == val) return root;
            if (root->val > val) root = root->left;
            else root = root->right;
        }
        return nullptr;
    }
};

操作

插入

不要求平衡就简单一些.

701. 二叉搜索树中的插入操作;

class Solution {
public:
    TreeNode* insertIntoBST(TreeNode* root, int val) {
        if (!root) return root = new TreeNode(val);
        auto cur{root};
        TreeNode* pre{};
        while (cur) {
            pre = cur;
            if (cur->val > val)
                cur = cur->left;
            else
                cur = cur->right;
        }
        if (pre->val > val)
            pre->left = new TreeNode(val);
        else
            pre->right = new TreeNode(val);
        return root;
    }
};

删除

450. 删除二叉搜索树中的节点;

参考了代码随想录. 感觉红黑树的很多操作都在这里面有缩影.

class Solution {
public:
    TreeNode* deleteNode(TreeNode* root, int key) {
        if (!root) return root;
        if (root->val == key) {
            if (!root->left && !root->right) {
                delete root;
                return nullptr;
            } else if (!root->left) {
                auto ans = root->right;
                delete root;
                return ans;
            } else if (!root->right) {
                auto ans = root->left;
                delete root;
                return ans;
            } else {
                auto cur = root->right;
                while (cur->left) cur = cur->left;
                cur->left = root->left;
                auto tmp = root;
                root = root->right;
                delete tmp;
                return root;
            }
        }
        if (root->val > key)
            root->left = deleteNode(root->left, key);
        else if (root->val < key)
            root->right = deleteNode(root->right, key);
        return root;
    }
};

修剪

669. 修剪二叉搜索树;(内存泄露需要考虑一下)

class Solution {
public:
    TreeNode* trimBST(TreeNode* root, int low, int high) {
        if (!root) return root;
        if (root->val < low) return trimBST(root->right, low, high);
        if (root->val > high) return trimBST(root->left, low, high);
        root->left = trimBST(root->left, low, high);
        root->right = trimBST(root->right, low, high);
        return root;
    }
};

迭代:

转换-构造

108. 将有序数组转换为二叉搜索树;

递归最快, 迭代法需要考虑三个队列.

class Solution {
public:
    TreeNode* sortedArrayToBST(vector<int>& nums) {
        function<TreeNode*(int, int)> f = [&](int l, int r) {
            if (l > r) return (TreeNode*)nullptr;
            int m = l + (r - l) / 2;
            return new TreeNode(nums[m], f(l, m - 1), f(m + 1, r));
        };
        return f(0, nums.size() - 1);
    }
};

迭代: (参考代码随想录)

class Solution {
public:
    TreeNode* sortedArrayToBST(vector<int>& nums) {
        if (nums.empty()) return nullptr;
        auto root = new TreeNode;
        queue<TreeNode*> q;
        queue<int> lq, rq;
        q.emplace(root);
        lq.emplace(0);
        rq.emplace(nums.size() - 1);
        while (!q.empty()) {
            auto cur = q.front();
            q.pop();
            auto l = lq.front();
            lq.pop();
            auto r = rq.front();
            rq.pop();
            auto m = l + (r - l) / 2;
            cur->val = nums[m];
            if (l <= m - 1) {
                cur->left = new TreeNode;
                q.emplace(cur->left);
                lq.emplace(l);
                rq.emplace(m - 1);
            }
            if (r >= m + 1) {
                cur->right = new TreeNode;
                q.emplace(cur->right);
                lq.emplace(m + 1);
                rq.emplace(r);
            }
        }
        return root;
    }
};

109. 有序链表转换二叉搜索树;

1008. 前序遍历构造二叉搜索树;

538. 把二叉搜索树转换为累加树; 1038. 从二叉搜索树到更大和树;

class Solution {
public:
    TreeNode* pre{};
    TreeNode* convertBST(TreeNode* root) { // 反中序遍历
        if (!root) return root;
        root->right = convertBST(root->right);
        root->val += pre ? pre->val : 0;
        pre = root;
        root->left = convertBST(root->left);
        return root;
    }
};

性质

501. 二叉搜索树中的众数;

class Solution {
public:
    vector<int> findMode(TreeNode* root) {
        vector<int> ans{};
        TreeNode* pre{};
        int cnt{}, max_cnt{};
        function<void(TreeNode*)> f = [&](TreeNode* node) {
            if (!node) return;
            f(node->left);
            if (pre && pre->val == node->val)
                ++cnt;
            else
                cnt = 1;
            pre = node;
            if (cnt == max_cnt) ans.emplace_back(node->val);
            if (cnt > max_cnt) {
                ans.clear(); // 关键
                max_cnt = cnt;
                ans.emplace_back(node->val);
            }
            f(node->right);
        };
        f(root);
        return ans;
    }
};

计数

差值计数

530. 二叉搜索树的最小绝对差;

class Solution {
public:
    int getMinimumDifference(TreeNode* root) {
        int ans{INT_MAX};
        TreeNode* pre{};
        function<void(TreeNode*)> f = [&](TreeNode* node) {
            if (!node) return;
            f(node->left);
            if (pre) ans = min(ans, node->val - pre->val);
            pre = node;
            f(node->right);
        };
        f(root);
        return ans;
    }
};

还有迭代:

class Solution {
public:
    int getMinimumDifference(TreeNode* root) {
        if (!root) return 0;
        int ans{INT_MAX};
        TreeNode* pre{};
        stack<TreeNode*> st;
        while (!st.empty() || root) {
            if (root) {
                st.emplace(root);
                root = root->left;
            } else {
                root = st.top();
                st.pop();
                if (pre) ans = min(ans, root->val - pre->val);
                pre = root;
                root = root->right;
            }
        }
        return ans;
    }
};

求和计数

1373. 二叉搜索子树的最大键值和;

树形 DP

1026. 节点与其祖先之间的最大差值;

 ```cpp
 ```

337. 打家劫舍 III; cpp

多叉树

class Node { // Definition
public:
    int val;
    vector<Node*> children;

    Node() {}

    Node(int _val) { val = _val; }

    Node(int _val, vector<Node*> _children) {
        val = _val;
        children = _children;
    }
};

559. N 叉树的最大深度;

class Solution {
public:
    int maxDepth(Node* root) {
        if (!root) return 0;
        int ans{1};
        for (auto c : root->children) ans = max(ans, maxDepth(c) + 1);
        return ans;
    }
};
// BFS
class Solution {
public:
    int maxDepth(Node* root) {
        if (!root) return 0;
        int ans{};
        queue<Node*> q;
        q.emplace(root);
        while (!q.empty()) {
            int n = q.size();
            while (n--) {
                auto node = q.front();
                q.pop();
                for (auto c : node->children) q.emplace(c);
            }
            ++ans;
        }
        return ans;
    }
};

上篇拓扑排序的c++实现

下篇差分数组c++实现与力扣题目总结