树

1.二叉树的深度

    int TreeDepth(TreeNode* root) {
        if (!root) return 0;
        int l = TreeDepth(root->left);
        int r = TreeDepth(root->right);
        return max(l, r) + 1;
    }

2.按之字形顺序打印二叉树

    vector<vector<int> > Print(TreeNode* root) {
        vector<vector<int>> res;
        if (!root) return res;
         
        queue<TreeNode*> q;
        int turn = 1;
        q.push(root);
        while (q.size()) {
            vector<int> path;
            int n = q.size();
            turn++;
            for (int i = 0; i < n; ++i) {
                auto node = q.front();
                q.pop();
                path.emplace_back(node->val);
                if (node->left) q.push(node->left);
                if (node->right) q.push(node->right);
            }
            if (turn & 1) {
                reverse(begin(path), end(path));
            }
            res.emplace_back(path);
        }
         
        return res;
    }

3.二叉搜索树的第K个节点

public:
    vector<int> vec;
    void traval(TreeNode* root) {
        if (!root) return;
        traval(root->left);
        vec.emplace_back(root->val);
        traval(root->right);
    }
    int KthNode(TreeNode* root, int k) {
        if (!root or k == 0) return -1;
        traval(root);
        if (vec.size() < k) return -1;
        return vec[k - 1];
    }
};

4.重建二叉树

前序遍历 + 中序遍历

    TreeNode* reConstructBinaryTree(vector<int> pre,vector<int> vin) {
        if (pre.empty()) return nullptr;
        auto root = new TreeNode(pre[0]);
        int idx = distance(vin.begin(), find(vin.begin(), vin.end(), pre[0]));
        vector<int> leftPre(pre.begin() + 1, pre.begin() + idx + 1);
        vector<int> rightPre(pre.begin() + idx + 1, pre.end());
        vector<int> leftVin(vin.begin(), vin.begin() + idx);
        vector<int> rightVin(vin.begin() + idx + 1, vin.end());
         
        root->left = reConstructBinaryTree(leftPre, leftVin);
        root->right = reConstructBinaryTree(rightPre, rightVin);
        return root;
    }

哈希表加速

class Solution {
    unordered_map<int, int> umap;
        TreeNode* dfs(vector<int>&pre, vector<int>& in, int pl, int pr, int il, int ir){
        if(pl > pr) return nullptr;
        //通过前序遍历找到根节点
        auto root = new TreeNode(pre[pl]);
        //找到根节点在中序遍历中的位置
        //该位置的左边就是根节点的左子树中序遍历，右边就是右子树的中序遍历
        int k = umap[pre[pl]] - il;
        //递归创建左右子树
        root->left = dfs(pre, in, pl + 1, pl + k, il, il + k - 1);
        root->right = dfs(pre, in, pl + k + 1, pr,il + k + 1, ir);
         
        return root;
    }
public:
    TreeNode* reConstructBinaryTree(vector<int> pre,vector<int> vin) {
        if (pre.empty()) return nullptr;
        int n = pre.size();
         
        for (int i = 0; i < vin.size(); ++i) {
            umap[vin[i]] = i;
        }
         
        return dfs(pre, vin, 0, n - 1, 0, n - 1);
    }
};

5.树的子结构

class Solution {
    bool isPart(TreeNode* p1, TreeNode* p2) {
        if (!p2) return true;
        if (!p1 or p1->val != p2->val) return false;
        return isPart(p1->left, p2->left) and isPart(p1->right, p2->right);
    }
public:
    bool HasSubtree(TreeNode* pRoot1, TreeNode* pRoot2) {
        if (!pRoot1 or !pRoot2) return false;
        if (isPart(pRoot1, pRoot2)) return true;
        return HasSubtree(pRoot1->left, pRoot2) or HasSubtree(pRoot1->right, pRoot2);
    }
};

6.二叉树的镜像

    TreeNode* Mirror(TreeNode* pRoot) {
        if (!pRoot) return nullptr;
        swap(pRoot->left, pRoot->right);
        Mirror(pRoot->left);
        Mirror(pRoot->right);
        return pRoot;
    }

7.二叉树中和为某一值的路径Ⅰ

    bool hasPathSum(TreeNode* root, int sum) {
        if (!root) return false;
        sum -= root->val;
        if (!root->left and !root->right) {
            if (sum == 0) return true;
            else return false;
        }
        return hasPathSum(root->left, sum) or hasPathSum(root->right, sum);
    }

8.二叉树中和为某一值的路径Ⅱ

class Solution {
    vector<vector<int>> res;
    vector<int> path;
    void dfs(TreeNode* root, int sum) {
        if (!root) return;
        path.push_back(root->val);
        sum -= root->val;
        //如果已经到最后一层了并且sum已经减到了0，那么就是答案
        if (!root->left && !root->right && !sum) res.push_back(path);
        dfs(root->left, sum);
        dfs(root->right, sum);
        path.pop_back();
    }
public:
    vector<vector<int>> FindPath(TreeNode* root,int sum) {
        dfs(root, sum);
        return res;
    }
};

9.二叉树中和为某一值的路径Ⅲ

class Solution {
    int res = 0;
    void dfs(TreeNode* root, int sum) {
        if (!root) return;
        if (sum == root->val) ++res;
        dfs(root->left, sum - root->val);
        dfs(root->right, sum - root->val);
    }
public:
    int FindPath(TreeNode* root, int sum) {
        if (!root) return res;
        dfs(root, sum);
        FindPath(root->left, sum);
        FindPath(root->right, sum);
        return res;
    }
};

10.二叉搜索树与双向链表

class Solution {
    vector<TreeNode*> vec;
    void inorder(TreeNode* pRoot) {
        if (!pRoot) return;
        inorder(pRoot->left);
        vec.emplace_back(pRoot);
        inorder(pRoot->right);
    }
public:
    TreeNode* Convert(TreeNode* pRoot) {
        if (!pRoot) return nullptr;
        inorder(pRoot);
        auto head = vec[0];
        auto cur = head;
        head->left = nullptr;
        for (int i = 1; i < vec.size(); ++i) {
            cur->right = vec[i];
            vec[i]->left = cur;
            cur = cur->right;
        }
        return head;
    }
};

11.序列化二叉树

感觉层序遍历更容易理解

class Solution {
public:
    char* Serialize(TreeNode *root) {    
        string s;
        queue<TreeNode*> q;
        q.push(root);
        while (q.size()) {
            auto node = q.front(); q.pop();
            if (!node) {
                s += "#,";
                continue;
            }
            s += to_string(node->val) + ',';
            q.push(node->left);
            q.push(node->right);
        }
        char *res = new char[s.size() + 1];
        strcpy(res, s.c_str());
        return res;
    }
    TreeNode* Deserialize(char *str) {
        if (!str or str[0] == '#') return nullptr;
        string s = str;
        queue<TreeNode*> q;
        TreeNode* root = new TreeNode(atoi(s.c_str()));
        s = s.substr(s.find_first_of(',') + 1);
        q.push(root);
        while (s.size() and q.size()) {
            auto node = q.front(); q.pop();
            
            if (s[0] == '#') {
                node->left = nullptr;
                s = s.substr(2);
            } else {
                node->left = new TreeNode(atoi(s.c_str()));
                q.push(node->left);
                s = s.substr(s.find_first_of(',') + 1);
            }
            
            if (s[0] == '#') {
                node->right = nullptr;
                s = s.substr(2);
            } else {
                node->right = new TreeNode(atoi(s.c_str()));
                q.push(node->right);
                s = s.substr(s.find_first_of(',') + 1);
            }
        }
        return root;
    }
};

12.对称二叉树

class Solution {
    bool check(TreeNode* l, TreeNode* r) {
        if (!l || !r) return !l and !r;
        if (l->val != r->val) return false;
        return check(l->left, r->right) and check(l->right, r->left);
    }
public:
    bool isSymmetrical(TreeNode* pRoot) {
        if (!pRoot) return true;
        return check(pRoot->left, pRoot->right);
    }
};

13.二叉树的先序中序后序遍历迭代法

class Solution {
    vector<int> preOrder(TreeNode* root) {
        if (!root) return {};
        vector<int> res;
        stack<TreeNode*> stk;
        stk.push(root);
        while (!stk.empty()) {
            auto node = stk.top(); stk.pop();
            res.push_back(node->val);
            if (node->right) stk.push(node->right);
            if (node->left) stk.push(node->left);
        }
        return res;
    }

    vector<int> inOrder(TreeNode* root) {
        if (!root) return {};
        vector<int> res;
        stack<TreeNode*> stk;
        auto cur = root;
        while (!stk.empty() or cur) {
            if (cur) {
                stk.push(cur);
                cur = cur->left;
            } else {
                cur = stk.top(); stk.pop();
                res.push_back(cur->val);
                cur = cur->right;
            }
        }
        return res;
    }
    
    vector<int> postOrder(TreeNode* root) {
        if (!root) return {};
        vector<int> res;
        stack<TreeNode*> stk;
        stk.push(root);
        while (!stk.empty()) {
            auto node = stk.top(); stk.pop();
            res.push_back(node->val);
            if (node->left) stk.push(node->left);
            if (node->right) stk.push(node->right);
        }
        reverse(res.begin(), res.end());
        return res;
    }
public:

    vector<vector<int> > threeOrders(TreeNode* root) {
        vector<vector<int>> res;
        res.push_back(preOrder(root));
        res.push_back(inOrder(root));
        res.push_back(postOrder(root));
        return res;
    }
};

14.二叉树的最近公共祖先

    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        //root为空或者遍历到空的叶节点
        if (!root) return root;
        if (p == root or q == root) return root;
        //左边找一找
        auto L = lowestCommonAncestor(root->left, p, q);
        //右边找一找
        auto R = lowestCommonAncestor(root->right, p, q);
        if (L and R) return root;
        else if (L) return L;
        else if (R) return R;
        return nullptr;
    }