【数据结构C++】树（六）_随笔

【数据结构C++】树（六）

文章目录

- 6.1 树
- - 6.1.1 递归
  - 6.1.2 层次遍历
  - 6.1.3 前中后序遍历
  - 6.1.4 二叉查找树(BST)
  - 6.1.5 Trie

6.1 树

6.1.1 递归

二叉树的最大深度： https://leetcode-cn.com/problems/maximum-depth-of-binary-tree/

class Solution {
public:
    int maxDepth(TreeNode* root) {
        if (root == nullptr) return 0;
        return max(maxDepth(root->left), maxDepth(root->right)) + 1;  
    }
};

复杂度分析
时间复杂度：O(n)，其中 n 为二叉树节点的个数。每个节点在递归中只被遍历一次。
空间复杂度：O(height)，其中 height 表示二叉树的高度。递归函数需要栈空间，而栈空间取决于递归的深度，因此空间复杂度等价于二		
叉树的高度。

class Solution {
public:
    int maxDepth(TreeNode* root) {
        if (root == nullptr) return 0;
       // queue是一种先进先出的数据结构 push：队尾加元素 pop：对头移除元素 back：返回最后一个元素 
       //front：返回第一个元素  empty:判断堆栈是否为空 size:返回栈的大小
        queue Q;  
        Q.push(root);
        int ans = 0;
        while (!Q.empty()) {
            int sz = Q.size();
            while (sz > 0) {
                TreeNode* node = Q.front();Q.pop();
                if (node->left) Q.push(node->left);
                if (node->right) Q.push(node->right);
                sz -= 1;
            }
            ans += 1;
        } 
        return ans;
    }
};

复杂度分析
时间复杂度：O(n)，其中 n 为二叉树的节点个数。与方法一同样的分析，每个节点只会被访问一次。
空间复杂度：此方法空间的消耗取决于队列存储的元素数量，其在最坏情况下会达到 O(n)。

平衡二叉树： https://leetcode-cn.com/problems/balanced-binary-tree/

class Solution {
public:
    int height(TreeNode* root) {
        if (root == NULL) {
            return 0;
        } else {
            return max(height(root->left), height(root->right)) + 1;
        }
    }

    bool isBalanced(TreeNode* root) {
        if (root == NULL) {
            return true;
        } else {
            return abs(height(root->left) - height(root->right)) <= 1 && isBalanced(root->left) && 
            isBalanced(root->right);
        }
    }
};

复杂度分析
时间复杂度：O(n^2)，其中 n 是二叉树中的节点个数。
最坏情况下，二叉树是满二叉树，需要遍历二叉树中的所有节点，时间复杂度是 O(n)。
对于节点 p，如果它的高度是 d，则 height(p) 最多会被调用 d 次（即遍历到它的每一个祖先节点时）。对于平均的情况，一棵树的高
度 h 满足 O(h)=O(logn)，因为 hd≤h，所以总时间复杂度为O(nlogn)。对于最坏的情况，二叉树形成链式结构，高度为 O(n)，此时总
时间复杂度为 O(n^2)。
空间复杂度：O(n)，其中 nn 是二叉树中的节点个数。空间复杂度主要取决于递归调用的层数，递归调用的层数不会超过 nn。

class Solution {
public:
    int height(TreeNode* root) {
        if (root == NULL) {
            return 0;
        }
        int leftHeight = height(root->left);
        int rightHeight = height(root->right);
        if (leftHeight == -1 || rightHeight == -1 || abs(leftHeight - rightHeight) > 1) {
            return -1;
        } else {
            return max(leftHeight, rightHeight) + 1;
        }
    }

    bool isBalanced(TreeNode* root) {
        return height(root) >= 0;
    }
};
复杂度分析
时间复杂度：O(n)，其中 n 是二叉树中的节点个数。使用自底向上的递归，每个节点的计算高度和判断是否平衡都只需要处理一次，最坏情
况下需要遍历二叉树中的所有节点，因此时间复杂度是 O(n)。
空间复杂度：O(n)，其中 n 是二叉树中的节点个数。空间复杂度主要取决于递归调用的层数，递归调用的层数不会超过 n。

二叉树的直径： https://leetcode-cn.com/problems/diameter-of-binary-tree/

class Solution {
    int ans;
    int depth(TreeNode* rt){
        if (rt == NULL) {
            return 0; // 访问到空节点了，返回0
        }
        int L = depth(rt->left); // 左儿子为根的子树的深度
        int R = depth(rt->right); // 右儿子为根的子树的深度
        ans = max(ans, L + R + 1); // 计算d_node即L+R+1 并更新ans
        return max(L, R) + 1; // 返回该节点为根的子树的深度
    }
public:
    int diameterOfBinaryTree(TreeNode* root) {
        ans = 1;
        depth(root);
        return ans - 1;
    }
};

复杂度分析
时间复杂度：O(N)，其中 N 为二叉树的节点数，即遍历一棵二叉树的时间复杂度，每个结点只被访问一次。
空间复杂度：O(Height)，其中Height 为二叉树的高度。由于递归函数在递归过程中需要为每一层递归函数分配栈空间，所以这里需要额外	
的空间且该空间取决于递归的深度，而递归的深度显然为二叉树的高度，并且每次递归调用的函数里又只用了常数个变量，所以所需空间复杂
度为 O(Height) 。

翻转二叉树： https://leetcode-cn.com/problems/invert-binary-tree/

class Solution {
public:
    TreeNode* invertTree(TreeNode* root) {
        if (root == nullptr) {                //递归终止的条件
            return nullptr;
        }
        TreeNode* left = invertTree(root->left);
        TreeNode* right = invertTree(root->right);
        root->left = right;
        root->right = left;
        return root;
    }
};

合并二叉树： https://leetcode-cn.com/problems/merge-two-binary-trees/

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

    }
};

class Solution {
public:
    TreeNode* mergeTrees(TreeNode* t1, TreeNode* t2) {
        if (t1 == nullptr) {
            return t2;
        }
        if (t2 == nullptr) {
            return t1;
        }
        auto merged = new TreeNode(t1->val + t2->val);
        auto q = queue();
        auto queue1 = queue();
        auto queue2 = queue();
        q.push(merged);
        queue1.push(t1);
        queue2.push(t2);
        while (!queue1.empty() && !queue2.empty()) {
            auto node = q.front(), node1 = queue1.front(), node2 = queue2.front();
            q.pop();
            queue1.pop();
            queue2.pop();
            auto left1 = node1->left, left2 = node2->left, right1 = node1->right, right2 = node2->right;
            if (left1 != nullptr || left2 != nullptr) {
                if (left1 != nullptr && left2 != nullptr) {
                    auto left = new TreeNode(left1->val + left2->val);
                    node->left = left;
                    q.push(left);
                    queue1.push(left1);
                    queue2.push(left2);
                } else if (left1 != nullptr) {
                    node->left = left1;
                } else if (left2 != nullptr) {
                    node->left = left2;
                }
            }
            if (right1 != nullptr || right2 != nullptr) {
                if (right1 != nullptr && right2 != nullptr) {
                    auto right = new TreeNode(right1->val + right2->val);
                    node->right = right;
                    q.push(right);
                    queue1.push(right1);
                    queue2.push(right2);
                } else if (right1 != nullptr) {
                    node->right = right1;
                } else {
                    node->right = right2;
                }
            }
        }
        return merged;
    }
};

路径总和： https://leetcode-cn.com/problems/path-sum/

class Solution {
public:
    bool hasPathSum(TreeNode *root, int sum) {
        if (root == nullptr) {              //递归的终止条件
            return false;
        }
        if (root->left == nullptr && root->right == nullptr) {
            return sum == root->val;
        }
        return hasPathSum(root->left, sum - root->val) || hasPathSum(root->right, sum - root->val);
    }
};

路径总和 III： https://leetcode-cn.com/problems/path-sum-iii/

class Solution {
public:
    int rootSum(TreeNode* root, int targetSum) {
        if (!root) {
            return 0;
        }

        int ret = 0;
        if (root->val == targetSum) {
            ret++;
        } 

        ret += rootSum(root->left, targetSum - root->val);
        ret += rootSum(root->right, targetSum - root->val);
        return ret;
    }

    int pathSum(TreeNode* root, int targetSum) {
        if (!root) {
            return 0;
        }
        
        int ret = rootSum(root, targetSum);
        ret += pathSum(root->left, targetSum);
        ret += pathSum(root->right, targetSum);
        return ret;
    }
};

另一棵树的子树： https://leetcode-cn.com/problems/subtree-of-another-tree/

class Solution {
public:
    bool check(TreeNode *o, TreeNode *t) {
        if (!o && !t) {
            return true;
        }
        if ((o && !t) || (!o && t) || (o->val != t->val)) {
            return false;
        }
        return check(o->left, t->left) && check(o->right, t->right);
    }

    bool dfs(TreeNode *o, TreeNode *t) {
        if (!o) {
            return false;
        }
        return check(o, t) || dfs(o->left, t) || dfs(o->right, t);
    }

    bool isSubtree(TreeNode *s, TreeNode *t) {
        return dfs(s, t);    // s， t表示两个指针  
    }
};

对称二叉树： https://leetcode-cn.com/problems/symmetric-tree/

class Solution {
public:
    bool check(TreeNode *p, TreeNode *q) {
        if (!p && !q) return true;
        if (!p || !q) return false;
        return p->val == q->val && check(p->left, q->right) && check(p->right, q->left);
    }

    bool isSymmetric(TreeNode* root) {
        return check(root, root);
    }
};

class Solution {
public:
    bool check(TreeNode *u, TreeNode *v) {
        queue  q;
        q.push(u); q.push(v);
        while (!q.empty()) {
            u = q.front(); q.pop();
            v = q.front(); q.pop();
            if (!u && !v) continue;
            if ((!u || !v) || (u->val != v->val)) return false;

            q.push(u->left); 
            q.push(v->right);

            q.push(u->right); 
            q.push(v->left);
        }
        return true;
    }

    bool isSymmetric(TreeNode* root) {
        return check(root, root);
    }
};

二叉树的最小深度： https://leetcode-cn.com/problems/minimum-depth-of-binary-tree/

class Solution {
public:
    int minDepth(TreeNode *root) {
        if (root == nullptr) {
            return 0;
        }

        if (root->left == nullptr && root->right == nullptr) {
            return 1;
        }

        int min_depth = INT_MAX;
        if (root->left != nullptr) {
            min_depth = min(minDepth(root->left), min_depth);
        }
        if (root->right != nullptr) {
            min_depth = min(minDepth(root->right), min_depth);
        }

        return min_depth + 1;
    }
};

左叶子之和: https://leetcode-cn.com/problems/sum-of-left-leaves/

class Solution {
public:
    bool isLeafNode(TreeNode* node) {
        return !node->left && !node->right;
    }

    int dfs(TreeNode* node) {
        int ans = 0;
        if (node->left) {
            ans += isLeafNode(node->left) ? node->left->val : dfs(node->left); 
        }
        if (node->right && !isLeafNode(node->right)) {
            ans += dfs(node->right);
        }
        return ans;
    }

    int sumOfLeftLeaves(TreeNode* root) {
        return root ? dfs(root) : 0;
    }
};

最长同值路径: https://leetcode-cn.com/problems/longest-univalue-path/

方法：深度优先搜索（DFS）
class Solution {
int res = 0;
public:
	int longestUnivaluePath(TreeNode *root)
	{
	    if (!root)
	        return 0;
	    longestPath(root);
	    return res;
	}
	
	int longestPath(TreeNode *root)
	{
	    if (!root)
	        return 0;
	    int left = longestPath(root->left), right = longestPath(root->right);
	    // 如果存在左子节点和根节点同值，更新左最长路径;否则左最长路径为0
	    if (root->left && root->val == root->left->val)
	        left++;
	    else
	        left = 0;
	    if (root->right && root->val == root->right->val)
	        right++;
	    else
	        right = 0;
	    res = max(res, left + right);
	    return max(left, right);
	}
};

6.1.2 层次遍历

使用 BFS(广度优先搜索) 进行层次遍历。不需要使用两个队列来分别存储当前层的节点和下一层的节点，
因为在开始遍历一层的节点时，当前队列中的节点数就是当前层的节点数，
只要控制遍历这么多节点数，就能保证这次遍历的都是当前层的节点。

二叉树的层平均值： https://leetcode-cn.com/problems/average-of-levels-in-binary-tree/

class Solution {
public:
    vector averageOfLevels(TreeNode* root) {
        auto averages = vector();
        auto q = queue();     
        q.push(root);
        while (!q.empty()) {
            double sum = 0;
            int size = q.size();
            for (int i = 0; i < size; i++) {
                auto node = q.front();
                q.pop();
                sum += node->val;
                auto left = node->left, right = node->right;
                if (left != nullptr) {
                    q.push(left);
                }
                if (right != nullptr) {
                    q.push(right);
                }
            }
            averages.push_back(sum / size); // push_back() 在Vector最后添加一个元素（参数为要插入的值）
        }
        return averages;
    }
};

找树左下角的值: https://leetcode-cn.com/problems/find-bottom-left-tree-value/

方法：BFS
class Solution {
public:
    int findBottomLeftValue(TreeNode* root) {
        int ans;
        queue q;  // 创建一个先进先出的栈
        q.push(root);
        while(!q.empty()){
            ans=q.front()->val;
            int n=q.size();
            while(n--){
                TreeNode* t=q.front();
                q.pop();
                if(t->left)q.push(t->left);
                if(t->right)q.push(t->right);
            }
        }
        return ans;
    }
};

6.1.3 前中后序遍历

// 1. 前序
void dfs(TreeNode root) {
    visit(root);
    dfs(root.left);
    dfs(root.right);
}

// 2. 中序
void dfs(TreeNode root) {
    dfs(root.left);
    visit(root);
    dfs(root.right);
}

// 3. 后序
void dfs(TreeNode root) {
    dfs(root.left);
    dfs(root.right);
    visit(root);
}

二叉树的前序遍历: https://leetcode-cn.com/problems/binary-tree-preorder-traversal/

class Solution {
public:
    void preorder(TreeNode *root, vector &res) {
        if (root == nullptr) {
            return;
        }
        res.push_back(root->val);
        preorder(root->left, res);
        preorder(root->right, res);
    }

    vector preorderTraversal(TreeNode *root) {
        vector res;
        preorder(root, res);
        return res;
    }
};

二叉树的中序遍历: https://leetcode-cn.com/problems/binary-tree-inorder-traversal/

class Solution {
public:
    void inorder(TreeNode* root, vector& res) {
        if (!root) {
            return;
        }
        inorder(root->left, res);
        res.push_back(root->val);
        inorder(root->right, res);
    }
    vector inorderTraversal(TreeNode* root) {
        vector res;
        inorder(root, res);
        return res;
    }
};

二叉树的后序遍历: https://leetcode-cn.com/problems/binary-tree-postorder-traversal/

class Solution {
public:
    void postorder(TreeNode *root, vector &res) {
        if (root == nullptr) {
            return;
        }
        postorder(root->left, res);
        postorder(root->right, res);
        res.push_back(root->val);
    }

    vector postorderTraversal(TreeNode *root) {
        vector res;
        postorder(root, res);
        return res;
    }
};

6.1.4 二叉查找树(BST)

二叉查找树（BST）：根节点大于等于左子树所有节点，小于等于右子树所有节点。
二叉查找树中序遍历有序。

二叉搜索树中的众数: https://leetcode-cn.com/problems/find-mode-in-binary-search-tree/

class Solution {
public:
    vector answer;
    int base, count, maxCount;

    void update(int x) {
        if (x == base) {
            ++count;
        } else {
            count = 1;
            base = x;
        }
        if (count == maxCount) {
            answer.push_back(base);
        }
        if (count > maxCount) {
            maxCount = count;
            answer = vector {base};
        }
    }

    void dfs(TreeNode* o) {
        if (!o) {
            return;
        }
        dfs(o->left);
        update(o->val);
        dfs(o->right);
    }

    vector findMode(TreeNode* root) {
        dfs(root);
        return answer;
    }
};

修剪二叉搜索树: https://leetcode-cn.com/problems/trim-a-binary-search-tree/

方法： 递归法
class Solution {
public:
    TreeNode* trimBST(TreeNode* root, int low, int high) {
        if (root == nullptr) return nullptr;
        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;
    }
};

二叉搜索树中第K小的元素: https://leetcode-cn.com/problems/kth-smallest-element-in-a-bst/

class Solution {
public:
    int kthSmallest(TreeNode* root, int k) {
        stack stack;
        while (root != nullptr || stack.size() > 0) {
            while (root != nullptr) {
                stack.push(root);
                root = root->left;
            }
            root = stack.top();
            stack.pop();
            --k;
            if (k == 0) {
                break;
            }
            root = root->right;
        }
        return root->val;
    }
};

6.1.5 Trie

Trie，又称前缀树或字典树，用于判断字符串是否存在或者是否具有某种字符串前缀。

实现 Trie (前缀树): https://leetcode-cn.com/problems/implement-trie-prefix-tree/

class Trie {
private:
    vector children;
    bool isEnd;

    Trie* searchPrefix(string prefix) {
        Trie* node = this;
        for (char ch : prefix) {
            ch -= 'a';
            if (node->children[ch] == nullptr) {
                return nullptr;
            }
            node = node->children[ch];
        }
        return node;
    }

public:
    Trie() : children(26), isEnd(false) {}

    void insert(string word) {
        Trie* node = this;
        for (char ch : word) {
            ch -= 'a';
            if (node->children[ch] == nullptr) {
                node->children[ch] = new Trie();
            }
            node = node->children[ch];
        }
        node->isEnd = true;
    }

    bool search(string word) {
        Trie* node = this->searchPrefix(word);
        return node != nullptr && node->isEnd;
    }

    bool startsWith(string prefix) {
        return this->searchPrefix(prefix) != nullptr;
    }
};

键值映射: https://leetcode-cn.com/problems/map-sum-pairs/

class MapSum {
public:
    MapSum() {

    }
    
    void insert(string key, int val) {
        cnt[key] = val;
    }
    
    int sum(string prefix) {
        int res = 0;
        for (auto & [key,val] : cnt) {
            if (key.substr(0, prefix.size()) == prefix) {
                res += val;
            }
        }
        return res;
    }
private:
    unordered_map cnt;
};

欢迎分享，转载请注明来源：内存溢出

原文地址: http://outofmemory.cn/zaji/5690611.html

【数据结构C++】树（六）

发表评论

评论列表（0条）