数据结构

代码随想录算法训练营第十八天

二叉树[Leetcode513找树左下角的值、Leetcode112路径总和、113路径总ii、Leetcode106从中序与后序遍历序列构造二叉树、105从前序与中序遍历序列构造二叉树]

Posted by ThreeStones1029 on April 20, 2024

[TOC]

第一题

Leetcode513找树左下角的值

解法一[递归]

  • 空间复杂度O(n)

  • 空间复杂度O(n)

class Solution {
public:
    int maxDepth = INT_MIN;   // 全局变量 记录最大深度
    int result;       // 全局变量 最大深度最左节点的数值
    void traversal(TreeNode* root, int depth){
        if (root->left == NULL && root->right == NULL){
            if (depth > maxDepth){
                maxDepth = depth;
                result = root->val; // 这里只有大于这个深度才会记录，实际上为前序遍历，在每次碰到新的叶子结点，且深度大于大于最大深度，则更新
                std::cout << result << std::endl;
            }
        }
        if (root->left){
            depth++;
            traversal(root->left, depth);
            depth--; // 回溯`
        }
        if (root->right){
            depth++;
            traversal(root->right, depth);
            depth--; // 回溯`
        }
    }

    int findBottomLeftValue(TreeNode* root) {
        traversal(root, 0);
        return result;
    }
};

解法二[层序遍历迭代法]

  • 空间复杂度O(n)
  • 空间复杂度O(n)
class Solution {
public:
    int findBottomLeftValue(TreeNode* root) {
        queue<TreeNode*> node_queue;
        node_queue.push(root);
        int result = 0;
        while (!node_queue.empty()){
            int size = node_queue.size();
            for (int i = 0; i < size; i++){
                TreeNode* cur = node_queue.front();
                if (cur->left != NULL) node_queue.push(cur->left);
                if (cur->right != NULL) node_queue.push(cur->right);
                node_queue.pop();
                if (i == 0) result = cur->val;
            }
        }
        return result;
    }
};

总结

  • 总感觉层序遍历是不是更简单，掌握的也更牢固。这题用层序遍历还是比较简单的，只要每次记录每层的第一个结点，最后结果自然就是最左下的结点。
  • 对于递归还是没有很好的写出来，感觉对于回溯用的不是很熟悉。

第二题

Leetcode112路径总和、113路径总ii

Leetcode112解法一[我的递归法]

  • 时间复杂度O(n)
  • 空间复杂度O(n)
class Solution {
public:
    void subPathSum(TreeNode* cur, vector<int>& path, vector<vector<int>>& result){
        path.push_back(cur->val);
        if (cur->left == NULL && cur->right == NULL){
            result.push_back(path);
        }
        if (cur->left){
            subPathSum(cur->left, path, result);
            path.pop_back();  // 回溯
        }
        if (cur->right){
            subPathSum(cur->right, path, result);
            path.pop_back();  // 回溯
        }
    }

    bool hasPathSum(TreeNode* root, int targetSum) {
        vector<vector<int>> result;
        vector<int> path;
        if (root == NULL) return false;
        subPathSum(root, path, result);
        for (int i = 0; i < result.size(); i++){
            int sum = 0;
            for (int j = 0; j < result[i].size(); j++){
                sum += result[i][j];
            }
            std::cout << sum << std::endl;
            if (sum == targetSum) return true;
        }
        return false;
    }
};

Leetcode112解法二[迭代法]

  • 时间复杂度O(n)
  • 空间复杂度O(n)
class Solution {
public:
    bool hasPathSum(TreeNode* root, int targetSum) {
        if (root == NULL) return false;
        stack<TreeNode*> node_stack;
        stack<vector<int>> all_path;
        node_stack.push(root);
        vector<int> path = {root->val};
        all_path.push(path);
        while (!node_stack.empty()){
            TreeNode* cur = node_stack.top();
            node_stack.pop();
            vector<int> path = all_path.top();
            all_path.pop();
            if (cur->left == NULL && cur->right == NULL){
                int sum = 0;
                for (int i = 0; i < path.size(); i++){
                    sum += path[i];
                }
                std::cout << sum << std::endl;
                if (sum == targetSum) return true;
            }
            if (cur->left) {
                path.push_back(cur->left->val);
                all_path.push(path);
                node_stack.push(cur->left);
                path.pop_back(); // 回溯
            }
            if (cur->right) {
                path.push_back(cur->right->val);
                all_path.push(path);
                node_stack.push(cur->right);
                path.pop_back();  // 回溯
            } 
        }
        return false;
    }
};

Leetcode112解法三[代码随想录的递归法]

  • 时间复杂度O(n)
  • 空间复杂度O(n)
class Solution {
public:
    bool subPathSum(TreeNode* cur, int sum){
        if (cur->left == NULL && cur->right == NULL && sum == 0) return true;
        if (cur->left == NULL && cur->right == NULL) return false;
        if (cur->left){
            // 回溯隐藏在其中
            if (subPathSum(cur->left, sum - cur->left->val)) return true;
        }
        if (cur->right){
            // 回溯隐藏在其中
            if (subPathSum(cur->right, sum - cur->right->val)) return true;
        }
        return false;
    }

    bool hasPathSum(TreeNode* root, int targetSum) {
        if (root == NULL) return false;
        return subPathSum(root, targetSum - root->val);
    }
};

Leetcode112解法四[代码随想录的迭代法]

  • 时间复杂度O(n)
  • 空间复杂度O(n)
class Solution {
public:
    bool hasPathSum(TreeNode* root, int targetSum) {
        if (root == NULL) return false;
        stack<pair<TreeNode*, int>> node_val_st;
        node_val_st.push(pair<TreeNode*, int>(root, root->val));
        while (!node_val_st.empty()){
            pair<TreeNode*, int> cur = node_val_st.top();
            node_val_st.pop();
            if (cur.first->left == NULL && cur.first->right == NULL && cur.second == targetSum) return true;
            if (cur.first->right){
                node_val_st.push(pair<TreeNode*, int>(cur.first->right, cur.first->right->val + cur.second));
            }
            if (cur.first->left){
                node_val_st.push(pair<TreeNode*, int>(cur.first->left, cur.first->left->val + cur.second));
            }
        }
        return false;
    }
};

Leetcode113解法一[我的递归法]

  • 时间复杂度O(n)
  • 空间复杂度O(n)
class Solution {
public:
    // 递归法
    void subPathSum(TreeNode* cur, vector<int>& single_path,vector<vector<int>>& result, int value){
        single_path.push_back(cur->val);
        if (cur->left == NULL && cur->right == NULL && value == 0) result.push_back(single_path);
        if (cur->left) {
            subPathSum(cur->left, single_path, result, value - cur->left->val);
            single_path.pop_back();  // 回溯
        }
        if (cur->right) {
            subPathSum(cur->right, single_path, result, value - cur->right->val);
            single_path.pop_back();  // 回溯
        }
    }
    vector<vector<int>> pathSum(TreeNode* root, int targetSum) {
        vector<vector<int>> result;
        vector<int> single_path;
        if (root == NULL) return result;
        subPathSum(root, single_path, result, targetSum - root->val);
        return result;
    }
};

Leetcode113解法二[我的迭代法–双栈]

  • 时间复杂度O(n)
  • 空间复杂度O(n)
class Solution {
public:
    vector<vector<int>> pathSum(TreeNode* root, int targetSum) {
        vector<vector<int>> result;
        stack<vector<int>> vector_st;
        if (root == NULL) return result;
        stack<TreeNode*> node_st;
        node_st.push(root);
        vector_st.push({root->val});
        while (!node_st.empty()){
            TreeNode* cur = node_st.top();
            node_st.pop();
            vector<int> single_path = vector_st.top();
            vector_st.pop();
            if (cur->left == NULL && cur->right == NULL){
                int sum = 0;
                for (int i = 0; i < single_path.size(); i++){
                    sum += single_path[i];
                }
                if (sum == targetSum){
                    result.push_back(single_path);
                }
            }
            if (cur->left){
                node_st.push(cur->left);
                single_path.push_back(cur->left->val);
                vector_st.push(single_path);
                single_path.pop_back();  // 回溯
            }
            if (cur->right){
                node_st.push(cur->right);
                single_path.push_back(cur->right->val);
                vector_st.push(single_path);
                single_path.pop_back();  // 回溯
            }

        }
        return result;
    }
};

总结

  • Leetcode112和前面的求所有路径一样，只是这样不需要返回所有，只需要返回是否存在特定的路径，但没有完全写出来，仿照前面的题目写的。
  • Leetcode112卡哥的方法确实更简洁,不管是迭代法还是递归法,学到了不少.

第三题

Leetcode106从中序与后序遍历序列构造二叉树、105从前序与中序遍历序列构造二叉树

Leetcode106解法一[递归法]

class Solution {
public:
    TreeNode* traversal(vector<int>& inorder, vector<int>& postorder) {
        // 第一步：如果数组大小为零的话，说明是空节点
        if (inorder.size() == 0) return NULL;
        // 第二步：如果不为空，那么取后序数组最后一个元素作为节点元素
        int rootvalue = postorder[postorder.size() - 1];
        TreeNode* root = new TreeNode(rootvalue);
        if (postorder.size() == 1) return root;
        // 第三步：找到后序数组最后一个元素在中序数组的位置，作为切割点
        int delimiterIndex;
        for (delimiterIndex = 0; delimiterIndex < inorder.size() - 1; delimiterIndex++){
            if (inorder[delimiterIndex] == rootvalue) break;
        }
        // 第四步：切割中序数组，切成中序左数组和中序右数组 （顺序别搞反了，一定是先切中序数组）
        // 坚持左闭右开
        vector<int> inorder_left(inorder.begin(), inorder.begin() + delimiterIndex);
        vector<int> inorder_right(inorder.begin() + delimiterIndex + 1, inorder.end());
        // 第五步：切割后序数组，切成后序左数组和后序右数组
        // 去除末尾元素,已经作为root
        postorder.resize(postorder.size() - 1); 
        vector<int> postorder_left(postorder.begin(), postorder.begin() + inorder_left.size());
        vector<int> postorder_right(postorder.begin() + inorder_left.size(), postorder.end());

        // 第六步：递归处理左区间和右区间
        root->left = traversal(inorder_left, postorder_left);
        root->right = traversal(inorder_right, postorder_right);
        return root;
    }


    TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) {
        if (inorder.size() == 0 || postorder.size() == 0) return NULL;
        return traversal(inorder, postorder);
    }
};

Leetcode106解法二[递归法]

class Solution {
public:
    TreeNode* traversal(vector<int>& inorder, int inorder_begin, int inorder_end, vector<int>& postorder, int postorder_begin, int postorder_end) {
        // 第一步：如果数组大小为零的话，说明是空节点
        if (inorder_end - inorder_begin == 0) return NULL;
        // 第二步：如果不为空，那么取后序数组最后一个元素作为节点元素
        int rootvalue = postorder[postorder_end - 1];
        TreeNode* root = new TreeNode(rootvalue);
        if (postorder_end - postorder_begin == 1) return root;
        // 第三步：找到后序数组最后一个元素在中序数组的位置，作为切割点
        int delimiterIndex;
        for (delimiterIndex = 0; delimiterIndex < inorder_end - 1; delimiterIndex++){
            if (inorder[delimiterIndex] == rootvalue) break;
        }
        // 第四步：切割中序数组，切成中序左数组和中序右数组 （顺序别搞反了，一定是先切中序数组）
        // 坚持左闭右开
        int left_inorder_begin = inorder_begin;
        int left_inorder_end = delimiterIndex;
        int right_inorder_begin = delimiterIndex + 1;
        int right_inorder_end = inorder_end;
        // 第五步：切割后序数组，切成后序左数组和后序右数组
        // 去除末尾元素,已经作为root
        int left_postorder_begin = postorder_begin;
        int left_postorder_end = postorder_begin + left_inorder_end - left_inorder_begin;
        int right_postorder_begin = left_postorder_end;
        int right_postorder_end = postorder_end - 1;
        // 第六步：递归处理左区间和右区间
        root->left = traversal(inorder, left_inorder_begin, left_inorder_end, postorder, left_postorder_begin, left_postorder_end);
        root->right = traversal(inorder, right_inorder_begin, right_inorder_end, postorder, right_postorder_begin, right_postorder_end);
        return root;
    }


    TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) {
        if (inorder.size() == 0 || postorder.size() == 0) return NULL;
        return traversal(inorder, 0, inorder.size(), postorder, 0, postorder.size());
    }
};

Leetcode105解法一[递归法-数组剪切]

class Solution {
public:
    TreeNode* traversal(vector<int>& preorder, vector<int>& inorder){
        // 第一步: 当preorder长度为0,返回空结点
        if (inorder.size() == 0) return NULL;
        // 第二步: preorder第一个结点为根结点
        int rootvalue = preorder[0];
        TreeNode* root = new TreeNode(rootvalue);
        if (preorder.size() == 1) return root;
        // 第三步,找到分割点
        int delimiterIndex;
        for (delimiterIndex = 0; delimiterIndex < inorder.size(); delimiterIndex++){
            if (inorder[delimiterIndex] == rootvalue) {
                break;
            }
        }
        // 第四步,划分中序为左子树与右子树
        vector<int> inorder_left(inorder.begin(), inorder.begin() + delimiterIndex);
        vector<int> inorder_right(inorder.begin() + delimiterIndex + 1, inorder.end());
        // 第五步,划分前序为左子树与右子树
        vector<int> preorder_left(preorder.begin() + 1, preorder.begin() + 1 + inorder_left.size());
        vector<int> preorder_right(preorder.begin() + 1 + inorder_left.size(), preorder.end());

        // 第六步
        root->left = traversal(preorder_left, inorder_left);
        root->right = traversal(preorder_right, inorder_right);
        return root;
    }
    TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
        if (preorder.size() == 0 || inorder.size() == 0) return NULL;
        return traversal(preorder, inorder);
    }
};

Leetcode105解法二[递归法-数组下标]

class Solution {
public:
    TreeNode* traversal(vector<int>& preorder, int preorder_begin, int preorder_end, vector<int>& inorder, int inorder_begin, int inorder_end){
        // 第一步: 当preorder长度为0,返回空结点
        if (inorder_end - inorder_begin == 0) return NULL;
        // 第二步: preorder第一个结点为根结点
        int rootvalue = preorder[preorder_begin];
        TreeNode* root = new TreeNode(rootvalue);
        if (preorder_end - preorder_begin == 1) return root;
        // 第三步,找到分割点
        int delimiterIndex;
        for (delimiterIndex = 0; delimiterIndex < inorder_end - inorder_begin; delimiterIndex++){
            if (inorder[inorder_begin + delimiterIndex] == rootvalue) {
                break;
            }
        }
        // 第四步,划分中序为左子树与右子树
        int inorder_left_begin = inorder_begin;
        int inorder_left_end = inorder_begin + delimiterIndex;
        int inorder_right_begin = inorder_begin + delimiterIndex + 1;
        int inorder_right_end = inorder_end;
        // 第五步,划分前序为左子树与右子树
        int preorder_left_begin = preorder_begin + 1;
        int preorder_left_end = preorder_begin + 1 + delimiterIndex;
        int preorder_right_begin = preorder_begin + 1 + delimiterIndex;
        int preorder_right_end = preorder_end;
        
        // 第六步
        root->left = traversal(preorder, preorder_left_begin, preorder_left_end, inorder, inorder_left_begin, inorder_left_end);
        root->right = traversal(preorder, preorder_right_begin, preorder_right_end, inorder, inorder_right_begin, inorder_right_end);
        return root;
    }
    TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
        if (preorder.size() == 0 || inorder.size() == 0) return NULL;
        return traversal(preorder, 0, preorder.size(), inorder, 0, inorder.size());
    }
};

总结

  • 使用下标来处理确实可以节省空间,不过需要处理好边界问题,还是需要保持好左闭右开或者左闭右闭.
  • 这题不太会写,虽然知道理论,但是还是需要看讲解,看完了中序后序构造二叉树来写中序与前序构造二叉树就比较容易了.
  • for循环时注意不要重复定义,重复定义会导致很难发现for循环里面的数实际是局部变量,很难发现.
  • 使用下标来做确实节省空间同时不用处理数据大小.

总结

这几天在忙着论文返修的意见,所以继续重新开始刷题.

CATALOG
    FEATURED TAGS
    感想 工具 医学图像处理 关键点检测 Ubuntu 环境搭建 pytorch Qt_and_VTK 个人博客 网络 数据结构 项目
    FRIENDS