跳至主要内容

268 篇文章 含有標籤「leetcode」

檢視所有標籤

120. Triangle

· 閱讀時間約 2 分鐘
/*
 * @lc app=leetcode id=120 lang=cpp
 *
 * [120] Triangle
 *
 * https://leetcode.com/problems/triangle/description/
 *
 * algorithms
 * Medium (57.96%)
 * Likes:    9775
 * Dislikes: 567
 * Total Accepted:    890K
 * Total Submissions: 1.5M
 * Testcase Example:  '[[2],[3,4],[6,5,7],[4,1,8,3]]'
 *
 * Given a triangle array, return the minimum path sum from top to bottom.
 *
 * For each step, you may move to an adjacent number of the row below. More
 * formally, if you are on index i on the current row, you may move to either
 * index i or index i + 1 on the next row.
 *
 *
 * Example 1:
 *
 *
 * Input: triangle = [[2],[3,4],[6,5,7],[4,1,8,3]]
 * Output: 11
 * Explanation: The triangle looks like:
 * ⁠  2
 * ⁠ 3 4
 * ⁠6 5 7
 * 4 1 8 3
 * The minimum path sum from top to bottom is 2 + 3 + 5 + 1 = 11 (underlined
 * above).
 *
 *
 * Example 2:
 *
 *
 * Input: triangle = [[-10]]
 * Output: -10
 *
 *
 *
 * Constraints:
 *
 *
 * 1 <= triangle.length <= 200
 * triangle[0].length == 1
 * triangle[i].length == triangle[i - 1].length + 1
 * -10^4 <= triangle[i][j] <= 10^4
 *
 *
 *
 * Follow up: Could you do this using only O(n) extra space, where n is the
 * total number of rows in the triangle?
 */

// @lc code=start
class Solution {
public:
    int minimumTotal(vector<vector<int>>& triangle)
    {
        int n = triangle.size();
        vector<int> dp = triangle.back();
        for (int i = n - 2; i >= 0; i--)
        {
            for (int j = 0; j <= i; j++)
            {
                dp[j] = triangle[i][j] + min(dp[j], dp[j + 1]);
            }
        }
        return dp[0];
    }
};
// @lc code=end
  • T: $O(N^2)$
  • S: $O(N)$

117. Populating Next Right Pointers in Each Node II

· 閱讀時間約 2 分鐘

Recursion

/*
// Definition for a Node.
class Node {
public:
    int val;
    Node* left;
    Node* right;
    Node* next;

    Node() : val(0), left(NULL), right(NULL), next(NULL) {}

    Node(int _val) : val(_val), left(NULL), right(NULL), next(NULL) {}

    Node(int _val, Node* _left, Node* _right, Node* _next)
        : val(_val), left(_left), right(_right), next(_next) {}
};
*/

class Solution {
public:
    Node* connect(Node* root)
    {
        if (!root) return nullptr;
        // 使用一個指標指向下一個節點
        Node* cur = root->next;

        while (cur)
        {
            if (cur->left)
            {
                cur = cur->left;
                break;
            }
            if (cur->right)
            {
                cur = cur->right;
                break;
            }
            cur = cur->next;
        }

        if (root->right)
        {
            root->right->next = cur;
        }
        if (root->left)
        {
            root->left->next = root->right ? root->right : cur;
        }
        connect(root->right);
        connect(root->left);
        return root;
    }
};

  • T: $O(n)$

  • S: $O(n)$

  • Iteration

/*
// Definition for a Node.
class Node {
public:
    int val;
    Node* left;
    Node* right;
    Node* next;

    Node() : val(0), left(NULL), right(NULL), next(NULL) {}

    Node(int _val) : val(_val), left(NULL), right(NULL), next(NULL) {}

    Node(int _val, Node* _left, Node* _right, Node* _next)
        : val(_val), left(_left), right(_right), next(_next) {}
};
*/

class Solution {
public:
    Node* connect(Node* root)
    {
        if (!root) return nullptr;

        queue<Node*> q{{root}};

        while (!q.empty())
        {
            int qSize = q.size();
            for (int i = 0; i < qSize; i++)
            {
                Node* node = q.front(); q.pop();
                if (i < qSize - 1)
                {
                    // 如果不是最末端的 node，node->next 指到下一個節點
                    node->next = q.front();
                }

                if (node->left) q.push(node->left);
                if (node->right) q.push(node->right);

            }
        }
        return root;
    }
};

  • T: $O(n)$

  • S: $O(n)$

  • Space O(1)

/*
// Definition for a Node.
class Node {
public:
    int val;
    Node* left;
    Node* right;
    Node* next;

    Node() : val(0), left(NULL), right(NULL), next(NULL) {}

    Node(int _val) : val(_val), left(NULL), right(NULL), next(NULL) {}

    Node(int _val, Node* _left, Node* _right, Node* _next)
        : val(_val), left(_left), right(_right), next(_next) {}
};
*/

class Solution {
public:
    Node* connect(Node* root) {
        Node* dummy = new Node(-1);
        Node* cur = dummy;
        Node* head = root;

        while (root)
        {
            if (root->left)
            {
                cur->next = root->left;
                cur = cur->next;
            }
            if (root->right)
            {
                cur->next = root->right;
                cur = cur->next;
            }

            root = root->next;

            if (!root)
            {
                cur = dummy;
                root = dummy->next;
                dummy->next = NULL;
            }
        }
        return head;
    }
};
  • T: $O(n)$
  • S: $O(1)$

116. Populating Next Right Pointers in Each Node

· 閱讀時間約 2 分鐘
  • recursion
/*
// Definition for a Node.
class Node {
public:
    int val;
    Node* left;
    Node* right;
    Node* next;

    Node() : val(0), left(NULL), right(NULL), next(NULL) {}

    Node(int _val) : val(_val), left(NULL), right(NULL), next(NULL) {}

    Node(int _val, Node* _left, Node* _right, Node* _next)
        : val(_val), left(_left), right(_right), next(_next) {}
};
*/

class Solution {
public:
    Node* connect(Node* root)
    {
        if (!root) return nullptr;

        if (root->left)
        {
            root->left->next = root->right;
        }

        if (root->right)
        {
            root->right->next = root->next ? root->next->left : nullptr;
        }

        connect(root->left);
        connect(root->right);
        return root;
    }
};

  • T: $O(n)$

  • S: $O(n)$

  • Iteration

/*
// Definition for a Node.
class Node {
public:
    int val;
    Node* left;
    Node* right;
    Node* next;

    Node() : val(0), left(NULL), right(NULL), next(NULL) {}

    Node(int _val) : val(_val), left(NULL), right(NULL), next(NULL) {}

    Node(int _val, Node* _left, Node* _right, Node* _next)
        : val(_val), left(_left), right(_right), next(_next) {}
};
*/

class Solution {
public:
    Node* connect(Node* root)
    {
        if (!root) return nullptr;

        queue<Node*> q{{root}};

        while (!q.empty())
        {
            int qSize = q.size();
            for (int i = 0; i < qSize; i++)
            {
                Node* node = q.front(); q.pop();
                if (i < qSize - 1)
                {
                    // 如果不是最末端的 node，node->next 指到下一個節點
                    node->next = q.front();
                }

                if (node->left) q.push(node->left);
                if (node->right) q.push(node->right);

            }
        }
        return root;
    }
};
  • T: $O(n)$
  • S: $O(n)$

112. Path Sum

· 閱讀時間約 2 分鐘

Recursion

/*
 * @lc app=leetcode id=112 lang=cpp
 *
 * [112] Path Sum
 *
 * https://leetcode.com/problems/path-sum/description/
 *
 * algorithms
 * Easy (51.70%)
 * Likes:    10144
 * Dislikes: 1170
 * Total Accepted:    1.8M
 * Total Submissions: 3.4M
 * Testcase Example:  '[5,4,8,11,null,13,4,7,2,null,null,null,1]\n22'
 *
 * Given the root of a binary tree and an integer targetSum, return true if the
 * tree has a root-to-leaf path such that adding up all the values along the
 * path equals targetSum.
 *
 * A leaf is a node with no children.
 *
 *
 * Example 1:
 *
 *
 * Input: root = [5,4,8,11,null,13,4,7,2,null,null,null,1], targetSum = 22
 * Output: true
 * Explanation: The root-to-leaf path with the target sum is shown.
 *
 *
 * Example 2:
 *
 *
 * Input: root = [1,2,3], targetSum = 5
 * Output: false
 * Explanation: There are two root-to-leaf paths in the tree:
 * (1 --> 2): The sum is 3.
 * (1 --> 3): The sum is 4.
 * There is no root-to-leaf path with sum = 5.
 *
 *
 * Example 3:
 *
 *
 * Input: root = [], targetSum = 0
 * Output: false
 * Explanation: Since the tree is empty, there are no root-to-leaf paths.
 *
 *
 *
 * Constraints:
 *
 *
 * The number of nodes in the tree is in the range [0, 5000].
 * -1000 <= Node.val <= 1000
 * -1000 <= targetSum <= 1000
 *
 *
 */

// @lc code=start
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    bool hasPathSum(TreeNode* root, int targetSum)
    {
        if (!root) return false;

        targetSum -= root->val;

        if (!root->left && !root->right) return targetSum == 0;

        return hasPathSum(root->left, targetSum) || hasPathSum(root->right, targetSum);
    }
};
// @lc code=end
  • T: $O(N)$
  • S: $O(N)$

Iteration

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    bool hasPathSum(TreeNode* root, int targetSum)
    {
        if (!root) return false;
        queue<pair<TreeNode*, int>> q;
        q.push({root, targetSum});
        while (!q.empty())
        {
            TreeNode* node = q.front().first;

            int sum = q.front().second; q.pop();

            if (!node) continue;

            sum -= node->val;

            if (sum == 0 && !node->left && !node->right)
            {
                return true;
            }

            if (node->left)
            {
                q.push({node->left, sum});
            }

            if (node->right)
            {
                q.push({node->right, sum});
            }
        }
        return false;
    }
};
  • T: $O(N)$
  • S: $O(N)$

110. Balanced Binary Tree

· 閱讀時間約 1 分鐘
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    bool isBalanced(TreeNode* root) {
        if(!root) return true;

        // 走訪左邊的樹
        int left = getHeight(root->left);

        // 走訪右邊的樹
        int right = getHeight(root->right);

        return abs(right - left) < 2 && isBalanced(root->left) && isBalanced(root->right);
    }
    int getHeight(TreeNode* root) {
        if(!root) return -1;
        // 每遞迴一次，height + 1
        return 1 + max(getHeight(root->left), getHeight(root->right));
    }
};
  • T: $O(N)$
  • S: $O(N)$

108. Convert Sorted Array to Binary Search Tree

· 閱讀時間約 1 分鐘

DFS

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    TreeNode* sortedArrayToBST(vector<int>& nums)
    {
        return dfs(nums, 0, nums.size() - 1);
    }

    TreeNode* dfs(vector<int>& nums, int left, int right)
    {
        if (left > right) return nullptr;
        int mid = (left + right) / 2;
        TreeNode* root = new TreeNode(nums[mid]);
        root->left = dfs(nums, left, mid - 1);
        root->right = dfs(nums, mid + 1, right);
        return root;
    }
};
  • T: $O(n)$
  • S: $O(\log n)$

105. Construct Binary Tree from Preorder and Inorder Traversal

· 閱讀時間約 2 分鐘
/*
 * @lc app=leetcode id=105 lang=cpp
 *
 * [105] Construct Binary Tree from Preorder and Inorder Traversal
 *
 * https://leetcode.com/problems/construct-binary-tree-from-preorder-and-inorder-traversal/description/
 *
 * algorithms
 * Medium (65.35%)
 * Likes:    15764
 * Dislikes: 569
 * Total Accepted:    1.5M
 * Total Submissions: 2.3M
 * Testcase Example:  '[3,9,20,15,7]\n[9,3,15,20,7]'
 *
 * Given two integer arrays preorder and inorder where preorder is the preorder
 * traversal of a binary tree and inorder is the inorder traversal of the same
 * tree, construct and return the binary tree.
 *
 *
 * Example 1:
 *
 *
 * Input: preorder = [3,9,20,15,7], inorder = [9,3,15,20,7]
 * Output: [3,9,20,null,null,15,7]
 *
 *
 * Example 2:
 *
 *
 * Input: preorder = [-1], inorder = [-1]
 * Output: [-1]
 *
 *
 *
 * Constraints:
 *
 *
 * 1 <= preorder.length <= 3000
 * inorder.length == preorder.length
 * -3000 <= preorder[i], inorder[i] <= 3000
 * preorder and inorder consist of unique values.
 * Each value of inorder also appears in preorder.
 * preorder is guaranteed to be the preorder traversal of the tree.
 * inorder is guaranteed to be the inorder traversal of the tree.
 *
 *
 */

// @lc code=start
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
private:
    int rootIndex = 0;
    unordered_map<int, int> indexMap;
public:
    TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder)
    {
        int n = preorder.size();

        for(int i = 0; i < n; ++i)
        {
            indexMap[inorder[i]] = i;
        }
        return build(preorder, 0, n - 1);
    }

    TreeNode* build(vector<int>& preorder, int left, int right)
    {
        if(left > right) return nullptr;

        int rootValue = preorder[rootIndex++];

        TreeNode* root = new TreeNode(rootValue);

        root->left = build(preorder, left, indexMap[rootValue] - 1);

        root->right = build(preorder, indexMap[rootValue] + 1, right);
        return root;
    }
};
// @lc code=end
  • T: $O(N)$
  • S: $O(N)$

104. Maximum Depth of Binary Tree

· 閱讀時間約 2 分鐘

Recursion

/*
 * @lc app=leetcode id=104 lang=cpp
 *
 * [104] Maximum Depth of Binary Tree
 *
 * https://leetcode.com/problems/maximum-depth-of-binary-tree/description/
 *
 * algorithms
 * Easy (76.33%)
 * Likes:    13462
 * Dislikes: 259
 * Total Accepted:    3.9M
 * Total Submissions: 5.1M
 * Testcase Example:  '[3,9,20,null,null,15,7]'
 *
 * Given the root of a binary tree, return its maximum depth.
 *
 * A binary tree's maximum depth is the number of nodes along the longest path
 * from the root node down to the farthest leaf node.
 *
 *
 * Example 1:
 *
 *
 * Input: root = [3,9,20,null,null,15,7]
 * Output: 3
 *
 *
 * Example 2:
 *
 *
 * Input: root = [1,null,2]
 * Output: 2
 *
 *
 *
 * Constraints:
 *
 *
 * The number of nodes in the tree is in the range [0, 10^4].
 * -100 <= Node.val <= 100
 *
 *
 */

// @lc code=start
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    int maxDepth(TreeNode* root) {
        if (!root) return 0;
        return 1 + max(maxDepth(root->left), maxDepth(root->right));
    }
};
// @lc code=end
  • T: $O(N)$
  • S: $O(\log N)$

Iteration

class Solution {
public:
    int maxDepth(TreeNode* root) {
        if (!root) return 0;
        queue<TreeNode*> q{{root}};
        int depth = 0;
        while (!q.empty()) {
            ++depth;
            int qSize = q.size();
            for (int i = 0; i < qSize; ++i) {
                TreeNode* node = q.front(); q.pop();
                if (node->left) q.push(node->left);
                if (node->right) q.push(node->right);
            }
        }
        return depth;
    }
};
  • T: $O(N)$
  • S: $O(\log N)$

103. Binary Tree Zigzag Level Order Traversal

· 閱讀時間約 2 分鐘
/*
 * @lc app=leetcode id=103 lang=cpp
 *
 * [103] Binary Tree Zigzag Level Order Traversal
 *
 * https://leetcode.com/problems/binary-tree-zigzag-level-order-traversal/description/
 *
 * algorithms
 * Medium (60.32%)
 * Likes:    11317
 * Dislikes: 324
 * Total Accepted:    1.4M
 * Total Submissions: 2.3M
 * Testcase Example:  '[3,9,20,null,null,15,7]'
 *
 * Given the root of a binary tree, return the zigzag level order traversal of
 * its nodes' values. (i.e., from left to right, then right to left for the
 * next level and alternate between).
 *
 *
 * Example 1:
 *
 *
 * Input: root = [3,9,20,null,null,15,7]
 * Output: [[3],[20,9],[15,7]]
 *
 *
 * Example 2:
 *
 *
 * Input: root = [1]
 * Output: [[1]]
 *
 *
 * Example 3:
 *
 *
 * Input: root = []
 * Output: []
 *
 *
 *
 * Constraints:
 *
 *
 * The number of nodes in the tree is in the range [0, 2000].
 * -100 <= Node.val <= 100
 *
 *
 */

// @lc code=start
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    vector<vector<int>> res;
    vector<vector<int>> zigzagLevelOrder(TreeNode* root) {
        if(!root) return res;
        levelOrder(root, 0);
        return res;
    }
    void levelOrder(TreeNode* root, int level) {
        if(!root) return;

        if(res.size() == level)
            res.push_back({});

        if(level % 2 == 0) {
            res[level].push_back(root->val);
        } else {
            res[level].insert(res[level].begin(), root->val);
        }
        levelOrder(root->left, 1 + level);
        levelOrder(root->right, 1 + level);
    }
};
// @lc code=end
  • T: $O(N)$
  • S: $O(N)$
class Solution {
public:
    vector<vector<int>> zigzagLevelOrder(TreeNode* root)
    {
        vector<vector<int>> res;
        queue<TreeNode*> q{{root}};
        bool leftToRight = true;
        while (!q.empty()) {
            vector<int> nodesWithinLevel;
            int qSize = q.size();
            for (int i = 0; i < qSize; i++) {
                TreeNode* node = q.front(); q.pop();
                if (!node) continue;
                if (leftToRight) {
                    nodesWithinLevel.push_back(node->val);
                } else {
                    nodesWithinLevel.insert(nodesWithinLevel.begin(), node->val);
                }
                q.push(node->left);
                q.push(node->right);
            }
            if (!nodesWithinLevel.empty()) {
                res.push_back(nodesWithinLevel);
                leftToRight = !leftToRight;
            }
        }
        return res;
    }
};
  • T: $O(N)$
  • S: $O(N)$