这种用指针表示的数据结构一般在leetcode上才会刷到，板子简单，浅浅总结一下。

二叉树(BST)

二叉树考点核心是深度优先搜索。

二叉树的定义

struct TreeNode {
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode() : val(0), left(nullptr), right(nullptr) {}
    TreeNode(int _val) : val(_val), lefft(nullptr), right(nullptr) {}
    TreeNode(int _val, TreeNode* _left, TreeNode* _right) : 
			val(_val), left(_left), right(_right) {}
}

二叉树的前序中序后序遍历-DFS

前序遍历

前序遍历根左右，前序指的是根在前

class Solution {
public:
    vector<int> preorderTraversal(TreeNode* root) {
        auto dfs = [
            f = [](auto&& self, TreeNode* root, vector<int>& res) -> void {
                if (root == nullptr) {
                    return;
                }
                res.push_back(root->val);
                self(self, root->left, res);
                self(self, root->right, res);
            }
        ] (TreeNode* root, vector<int>& res) -> void {return f(f, root, res);};

        vector<int> res;
        dfs(root, res);
        return res;
    }
};

更新，加个引用&，可以这么递归调用lambda

class Solution {
public:
    vector<int> preorderTraversal(TreeNode* root) {
        function<void (TreeNode*, vector<int>&)> dfs = [&](TreeNode* root, vector<int>& res) {
            if (root == nullptr) {
                return;
            }
            res.push_back(root->val);
            dfs(root->left, res);
            dfs(root->right, res);
        };

        vector<int> res;
        dfs(root, res);
        return res;
    }
};

中序遍历

中序遍历左根右，中序指的是根在中

class Solution {
public:
    vector<int> inorderTraversal(TreeNode* root) {
        auto dfs = [
            f = [](auto&& self, TreeNode* root, vector<int>& res) -> void {
                if (root == nullptr) {
                    return;
                }
                self(self, root->left, res);
                res.push_back(root->val);
                self(self, root->right, res);
            }
        ](TreeNode* root, vector<int>& res) {return f(f, root, res);};

        vector<int> res;
        dfs(root, res);
        return res;
    }
};

class Solution {
public:
    vector<int> inorderTraversal(TreeNode* root) {
        function<void (TreeNode*, vector<int>&)> dfs = [&](TreeNode* root, vector<int>& res) {
            if (root == nullptr) {
                return;
            }
            dfs(root->left, res);
            res.push_back(root->val);
            dfs(root->right, res);
        };

        vector<int> res;
        dfs(root, res);
        return res;
    }
};

后续遍历

后序遍历左右根，后序指的是根在后

class Solution {
public:
    vector<int> postorderTraversal(TreeNode* root) {
        auto dfs = [
            f = [](auto&& self, TreeNode* root, vector<int>& res) -> void {
                if (root == nullptr) {
                    return;
                }
                self(self, root->left, res);
                self(self, root->right, res);
                res.push_back(root->val);
            }
        ](TreeNode* root, vector<int>& res) {return f(f, root, res);};

        vector<int> res;
        dfs(root, res);
        return res;
    }
};

class Solution {
public:
    vector<int> postorderTraversal(TreeNode* root) {
        function<void (TreeNode*, vector<int>&)> dfs = [&](TreeNode* root, vector<int>& res) {
            if (root == nullptr) {
                return;
            }
            dfs(root->left, res);
            dfs(root->right, res);
            res.push_back(root->val);
        };

        vector<int> res;
        dfs(root, res);
        return res;
    }
};

二叉树的层次遍历-BFS

队列，不要想太多哈哈

class Solution {
public:
    vector<vector<int>> levelOrder(TreeNode* root) {
        if (root == nullptr) return {};
        vector<vector<int>> res;
        queue<TreeNode*> q;
        q.push(root);
        while (!q.empty()) {
            int sz = q.size();
            vector<int> tmp;
            for (int i = 0; i < sz; i++) {
                auto t = q.front(); q.pop();
                tmp.push_back(t->val);
                if (t->left != nullptr) q.push(t->left);
                if (t->right != nullptr) q.push(t->right);
            }
            res.push_back(tmp);
        }
        return res;
    }
};

---

LeetCode二叉树题目

如何在路径中确定祖孙关系?

删除给定值的叶子节点

https://leetcode.cn/problems/delete-leaves-with-a-given-value/

class Solution {
public:
    TreeNode* removeLeafNodes(TreeNode* root, int target) {
        if (root == nullptr) {
            return nullptr;
        }
        TreeNode* left = removeLeafNodes(root->left, target);
        TreeNode* right = removeLeafNodes(root->right, target);
        root->left = left;
        root->right = right;
        if (left == nullptr && right == nullptr) {
            if (root->val == target) {
                return nullptr;
            }
        }
        return root;
   }
};

二叉树展开为链表

https://leetcode.cn/problems/flatten-binary-tree-to-linked-list/

class Solution {
public:
    void flatten(TreeNode* root) {
        function<TreeNode*(TreeNode*)> dfs = [&](TreeNode* root) -> TreeNode* {
            if (root == nullptr || (root->left == nullptr && root->right == nullptr) ) return root;
            TreeNode* left = dfs(root->left);
            TreeNode* right = dfs(root->right);
            if (left != nullptr) {
                left->right = root->right;
                root->right = root->left;
                root->left = nullptr;
            }
            return right == nullptr ? left : right;
        };
        dfs(root);
    }
};

求根节点到叶节点数字之和

https://leetcode.cn/problems/sum-root-to-leaf-numbers/

路径贡献

二叉树中分配硬币

https://leetcode.cn/problems/distribute-coins-in-binary-tree/

return值的含义是需要从当前节点拿走多少个硬币

class Solution {
public:
    int distributeCoins(TreeNode* root) {
        int res = 0;
        function<int(TreeNode*)> dfs = [&] (TreeNode* root) ->int {
            if (root == nullptr) return 0;
            int left = dfs(root->left);
            int right = dfs(root->right);
            res += abs(left) + abs(right);
            return root->val + left + right - 1;
        };
        dfs(root);
        return res;
    }
};

N叉树

N叉树的前序中序后序遍历-DFS

前序遍历

中序遍历

后续遍历

N叉树的层次遍历-BFS