树与二叉树

二叉树遍历

层序遍历（本质是广度优先遍历(BFS)）

class Solution {
public:
    
    vector<vector<int>> levelOrder(TreeNode* root) {
        vector<vector<int>> ans;
        if(!root) return ans;

        queue<TreeNode*> q;
        q.push(root);

        while(!q.empty()){
            // 当前层的节点个数
            int len = q.size();
            ans.emplace_back(vector<int> ());
            // 遍历当前层的节点
            for(int i=1; i<=len; i++){
                TreeNode* node = q.front();
                q.pop();
                ans.back().emplace_back(node->val);
                // 添加下一层的节点
                if(node->left) q.push(node->left);
                if(node->right) q.push(node->right);
            }
                
        }
        return ans;
    }
};

先序遍历

** 先序 中序 后序遍历都是对树的深度优先遍历(DFS)** 递归实现

class Solution {
public:
    vector<int> preinorderTraversal(TreeNode* root) {
        vector<int> ans;
        inorder(root, ans);
        return ans;
    }   
    void inorder(TreeNode* root, vector<int>& res){
        if(!root){
            return;
        }
        // 节点 左 右
        res.push_back(root->val);
        inorder(root->left, res);
        inorder(root->right, res);
    }
};

非递归：利用栈实现，注意入栈的顺序（先右子树入栈，这样确保栈顶是左子树）。

class Solution {
public:
    vector<int> preinorderTraversal(TreeNode* root) {
        vector<int> ans;
        stack<TreeNode*> sk;
        TreeNode* current = root;

        if(current == nullptr) return ans;

        while(!sk.empty() || current != nullptr){
            current = sk.top();
            sk.pop();
            ans.push_back(current->val);
            if(current->right) sk.push(current->right);
            if(current->left) sk.push(current->left);
        }
        return ans;
    }
};

中序遍历

递归实现

class Solution {
public:
    vector<int> inorderTraversal(TreeNode* root) {
        vector<int> ans;
        inorder(root, ans);
        return ans;
    }   
    void inorder(TreeNode* root, vector<int>& res){
        if(!root){
            return;
        }
        // 左 节点 右
        inorder(root->left, res);
        res.push_back(root->val);
        inorder(root->right, res);
    }
};

非递归：利用栈进行存储节点

class Solution {
public:
    vector<int> inorderTraversal(TreeNode* root) {
        vector<int> ans;
        TreeNode* current = root;
        stack<TreeNode*> sk;

        while(!sk.empty() || current != nullptr){
            // 当前节点非空，入栈且转向左子树
            while(current != nullptr){
                sk.push(current);
                current = current->left;
            }
            if(!sk.empty()){
                // 取出栈顶节点，最左侧节点
                current = sk.top();
                sk.pop();
                ans.push_back(current->val);
                // 转向其他右边子树
                current = current->right;
            }
        }
        return ans;
    }   
};

后序遍历

递归的实现

class Solution {
public:
    vector<int> preinorderTraversal(TreeNode* root) {
        vector<int> ans;
        inorder(root, ans);
        return ans;
    }   
    void inorder(TreeNode* root, vector<int>& res){
        if(!root){
            return;
        }
        //  左 右 节点
        inorder(root->left, res);
        inorder(root->right, res);
        res.push_back(root->val);
    }
};

后序遍历需要考虑前驱节点的问题。

class Solution {
public:
    vector<int> inorderTraversal(TreeNode* root) {
        vector<int> ans;
        TreeNode* current = root;
        TreeNode* pre = nullptr;
        stack<TreeNode*> sk;
        sk.push(current);

        while(!sk.empty() ){
            current = sk.top();
            
            if((current->left == nullptr && current  != nullptr) || (pre != nullptr && current->left == pre)|| (pre != nullptr && current->right == pre)){
                // 取出栈顶节点，最左侧节点
                ans.push_back(current->val);
                sk.pop();
                pre = current;
            }else{
                // 这里也是要先压入右节点
                if(current->right != nullptr) sk.push(current->right);
                if(current->left != nullptr) sk.push(current->left);
            }
        }
        return ans;
    }   
};

求路径问题的思路

判定树中是否存在和sum的路径

class Solution {
public:
    bool hasPathSum(TreeNode *root, int sum) {
        if (root == nullptr) {
            return false;
        }
        queue<TreeNode *> que_node;
        queue<int> que_val;
        que_node.push(root);
        que_val.push(root->val);
        while (!que_node.empty()) {
            TreeNode *now = que_node.front();
            int temp = que_val.front();
            que_node.pop();
            que_val.pop();
            if (now->left == nullptr && now->right == nullptr) {
                if (temp == sum) {
                    return true;
                }
                continue;
            }
            // 保存左边路径的值
            if (now->left != nullptr) {
                que_node.push(now->left);
                que_val.push(now->left->val + temp);
            }
            // 保存右边路径的值
            if (now->right != nullptr) {
                que_node.push(now->right);
                que_val.push(now->right->val + temp);
            }
        }
        return false;
    }
};

二叉搜索树

AVL树(平衡二叉树)

高度平衡二叉树定义为：一个二叉树每个节点的左右两个子树的高度差的绝对值不超过1（Balance Factor）。 某些极端的情况下（如在插入的序列是有序的时），二叉搜索树将退化成近似链或链，此时，其操作的时间复杂度将退化成线性的，即O(n)。然而平衡树为log2n，因此调整成平衡的二叉搜索树效率会更高。 判定平衡

class Solution {
public:
    bool isBalanced(TreeNode* root) {
        return treeHeight(root) >= 0;
    }
    int treeHeight(TreeNode* root){
        if(root == nullptr) return 0;

        int left = treeHeight(root->left);
        int right = treeHeight(root->right);

        // 在最大深度的判定上加入了平衡的判定
        if(left == -1 || right == -1 || abs(left-right) > 1){
            return -1;
        }

        return max(left, right) + 1;
    }
};

B树

B+树

红黑树