Ascendlogo

Posted on Edited on In

112.Path Sum

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:

img

1
2
3
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:

img

1
2
3
4
5
6
Input: root = [1,2,3], targetSum = 5
Output: false
Explanation: There 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:

1
2
3
Input: root = [], targetSum = 0
Output: false
Explanation: Since the tree is empty, there are no root-to-leaf paths.

递归法：

时间复杂度：O(N),其中N是树的节点数

空间复杂度：O(H),其中H是树的高度

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
public:
    bool hasPathSum(TreeNode *root, int targetSum) {
        if (root == nullptr) {
            return false;
        }
        if (root->left == nullptr && root->right == nullptr) {
            return targetSum == root->val;
        }
        return hasPathSum(root->left, targetSum - root->val) ||
               hasPathSum(root->right, targetSum - root->val);
    }
};

广度优先遍历：

时间复杂度：O(N)

空间复杂度：O(N)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
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;
    }
};

Posted on Edited on In

111.Minimum Depth of Binary Tree

给定一个二叉树，找出其最小深度。

最小深度是从根节点到最近叶子节点的最短路径上的节点数量。

说明：叶子节点是指没有子节点的节点。

示例 1：

img

1
2
输入：root = [3,9,20,null,null,15,7]
输出：2

示例 2：

1
2
输入：root = [2,null,3,null,4,null,5,null,6]
输出：5

深度优先遍历：

时间复杂度：O(N)，N为节点数

空间复杂度：O(H)，H为树高度

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
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;
    }
};

广度优先遍历：

时间复杂度：O(N)

空间复杂度：O(N)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
class Solution {
public:
    int minDepth(TreeNode *root) {
        if (root == nullptr) {
            return 0;
        }

        queue<pair<TreeNode *, int> > que;
        que.emplace(root, 1);
        while (!que.empty()) {
            TreeNode *node = que.front().first;
            int depth = que.front().second;
            que.pop();
            if (node->left == nullptr && node->right == nullptr) {
                return depth;
            }
            if (node->left != nullptr) {
                que.emplace(node->left, depth + 1);
            }
            if (node->right != nullptr) {
                que.emplace(node->right, depth + 1);
            }
        }

        return 0;
    }
};

Posted on Edited on In

110.Balanced Binary Tree

Given a binary tree, determine if it is height-balanced

Example 1:

img

1
2
Input: root = [3,9,20,null,null,15,7]
Output: true

Example 2:

img

1
2
Input: root = [1,2,2,3,3,null,null,4,4]
Output: false

Example 3:

1
2
Input: root = []
Output: true

时间复杂度：O(n)
空间复杂度：O(n)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public:
    bool isBalanced(TreeNode* root) {
        return height(root) >= 0;
    }
    int height(TreeNode* root) {
        if (root == nullptr)return 0;
        int left_height = height(root->left);
        int right_height = height(root->right);
        if (left_height == -1 || right_height == -1 || abs(left_height - right_height) > 1) {
            return -1;
        }
        else {
            return max(left_height, right_height) + 1;
        }
    }
};

Posted on Edited on In

108. Convert Sorted Array to Binary Search Tree

Given an integer array nums where the elements are sorted in ascending order, convert it to a

height-balanced binary search tree.

Example 1:

img

1
2
3
Input: nums = [-10,-3,0,5,9]
Output: [0,-3,9,-10,null,5]
Explanation: [0,-10,5,null,-3,null,9] is also accepted:

Example 2:

img

1
2
3
Input: nums = [1,3]
Output: [3,1]
Explanation: [1,null,3] and [3,1] are both height-balanced BSTs.

中序遍历：

  • 时间复杂度：O(n)
  • 空间复杂度：O(log⁡ n)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public:
    TreeNode* sortedArrayToBST(vector<int>& nums) {
        return helper(nums, 0, nums.size() - 1);
    }

    TreeNode* helper(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 = helper(nums, left, mid - 1);
        root->right = helper(nums, mid + 1, right);
        return root;
    }
};

Posted on Edited on In

104.Maximum Depth of Binary Tree

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:

img

1
2
Input: root = [3,9,20,null,null,15,7]
Output: 3

Example 2:

1
2
Input: root = [1,null,2]
Output: 2

深度优选搜索：

时间复杂度：O(n)

空间复杂度：O(height)

1
2
3
4
int maxDepth(TreeNode* root) {
    if (root == nullptr) return 0;
    return max(maxDepth(root->left), maxDepth(root->right)) + 1;
}

广度优先搜索：

时间复杂度：O(n)

空间复杂度：O(n)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
int maxDepth(TreeNode* root) {
    if (root == nullptr) return 0;
    queue<TreeNode*> 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;
}

Posted on Edited on In

101.Symmetric Tree

Given the root of a binary tree, check whether it is a mirror of itself (i.e., symmetric around its center).

Example 1:

img

1
2
Input: root = [1,2,2,3,4,4,3]
Output: true

Example 2:

img

1
2
Input: root = [1,2,2,null,3,null,3]
Output: false

迭代法：

时间复杂度：O(n)

空间复杂度：O(n)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
bool check(TreeNode *u, TreeNode *v) {
    queue <TreeNode*> 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);
}

递归法：

时间复杂度：O(n)

空间复杂度：O(n)

1
2
3
4
5
6
7
8
9
10
11
12
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);
    }
};

Posted on Edited on In

100.Same Tree

Given the roots of two binary trees p and q, write a function to check if they are the same or not.

Two binary trees are considered the same if they are structurally identical, and the nodes have the same value.

Example 1:

img

1
2
Input: p = [1,2,3], q = [1,2,3]
Output: true

Example 2:

img

1
2
Input: p = [1,2], q = [1,null,2]
Output: false

Example 3:

img

1
2
Input: p = [1,2,1], q = [1,1,2]
Output: false

深度优先搜索：

时间复杂度：O(min⁡(m,n))

空间复杂度：O(min⁡(m,n))

1
2
3
4
5
6
7
8
9
10
11
bool isSameTree(TreeNode* p, TreeNode* q) {
    if (p == nullptr && q == nullptr) {
        return true;
    } else if (p == nullptr || q == nullptr) {
        return false;
    } else if (p->val != q->val) {
        return false;
    } else {
        return isSameTree(p->left, q->left) && isSameTree(p->right, q->right);
    }
}

广度优先搜索：

时间复杂度：O(min⁡(m,n))

空间复杂度：O(min⁡(m,n))

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
bool isSameTree(TreeNode* p, TreeNode* q) {
    if (p == nullptr && q == nullptr) {
        return true;
    } else if (p == nullptr || q == nullptr) {
        return false;
    }
    queue <TreeNode*> queue1, queue2;
    queue1.push(p);
    queue2.push(q);
    while (!queue1.empty() && !queue2.empty()) {
        auto node1 = queue1.front();
        queue1.pop();
        auto node2 = queue2.front();
        queue2.pop();
        if (node1->val != node2->val) {
            return false;
        }
        auto left1 = node1->left, right1 = node1->right, left2 = node2->left, right2 = node2->right;
        if ((left1 == nullptr) ^ (left2 == nullptr)) {
            return false;
        }
        if ((right1 == nullptr) ^ (right2 == nullptr)) {
            return false;
        }
        if (left1 != nullptr) {
            queue1.push(left1);
        }
        if (right1 != nullptr) {
            queue1.push(right1);
        }
        if (left2 != nullptr) {
            queue2.push(left2);
        }
        if (right2 != nullptr) {
            queue2.push(right2);
        }
    }
    return queue1.empty() && queue2.empty();
}

Posted on Edited on In

94.Binary Tree In order Traversal

Given the root of a binary tree, return the in order traversal of its nodes’ values.

Example 1:

img

1
2
Input: root = [1,null,2,3]
Output: [1,3,2]

Example 2:

1
2
Input: root = []
Output: []

Example 3:

1
2
Input: root = [1]
Output: [1]

递归法：

时间复杂度：O(n)

空间复杂度：O(n)

1
2
3
4
5
6
7
8
9
10
11
12
13
void inorder(TreeNode* root, vector<int>& res) {
    if (!root) {
        return;
    }
    inorder(root->left, res);
    res.push_back(root->val);
    inorder(root->right, res);
}
vector<int> inorderTraversal(TreeNode* root) {
    vector<int> res;
    inorder(root, res);
    return res;
}

迭代法：

时间复杂度：O(n)

空间复杂度：O(n)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
vector<int> inorderTraversal(TreeNode* root) {
    vector<int> res;
    stack<TreeNode*> stk;
    while (root != nullptr || !stk.empty()) {
        while (root != nullptr) {
            stk.push(root);
            root = root->left;
        }
        root = stk.top();
        stk.pop();
        res.push_back(root->val);
        root = root->right;
    }
    return res;
}

Morris 中序遍历：

时间复杂度：O(n)

空间复杂度：O(1)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
vector<int> inorderTraversal(TreeNode* root) {
    vector<int> res;
    TreeNode *predecessor = nullptr;

    while (root != nullptr) {
        if (root->left != nullptr) {
            // predecessor 节点就是当前 root 节点向左走一步，然后一直向右走至无法走为止
            predecessor = root->left;
            while (predecessor->right != nullptr && predecessor->right != root) {
                predecessor = predecessor->right;
            }

            // 让 predecessor 的右指针指向 root，继续遍历左子树
            if (predecessor->right == nullptr) {
                predecessor->right = root;
                root = root->left;
            }
            // 说明左子树已经访问完了，我们需要断开链接
            else {
                res.push_back(root->val);
                predecessor->right = nullptr;
                root = root->right;
            }
        }
        // 如果没有左孩子，则直接访问右孩子
        else {
            res.push_back(root->val);
            root = root->right;
        }
    }
    return res;
}

Posted on Edited on In

88.Merge Sorted Array

You are given two integer arrays nums1 and nums2, sorted in non-decreasing order, and two integers m and n, representing the number of elements in nums1 and nums2 respectively.

Merge nums1 and nums2 into a single array sorted in non-decreasing order.

The final sorted array should not be returned by the function, but instead be stored inside the array nums1. To accommodate this, nums1 has a length of m + n, where the first m elements denote the elements that should be merged, and the last n elements are set to 0 and should be ignored. nums2 has a length of n.

Example 1:

1
2
3
4
Input: nums1 = [1,2,3,0,0,0], m = 3, nums2 = [2,5,6], n = 3
Output: [1,2,2,3,5,6]
Explanation: The arrays we are merging are [1,2,3] and [2,5,6].
The result of the merge is [1,2,2,3,5,6] with the underlined elements coming from nums1.

Example 2:

1
2
3
4
Input: nums1 = [1], m = 1, nums2 = [], n = 0
Output: [1]
Explanation: The arrays we are merging are [1] and [].
The result of the merge is [1].

Example 3:

1
2
3
4
5
Input: nums1 = [0], m = 0, nums2 = [1], n = 1
Output: [1]
Explanation: The arrays we are merging are [] and [1].
The result of the merge is [1].
Note that because m = 0, there are no elements in nums1. The 0 is only there to ensure the merge result can fit in nums1.

个人解答：

时间复杂度：O((m+n)log(m+n))（套用快速排序）

空间复杂度：O(1)

1
2
3
4
5
6
void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) {
    for (int i = 0; i != n; ++i) {
        nums1[m + i] = nums2[i];
    }
    sort(nums1.begin(), nums1.end());
}

逆向双指针：

时间复杂度：O(m+n)。

空间复杂度：O(1)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) {
    int p1 = m - 1, p2 = n - 1;
    int tail = m + n - 1;
    int cur;
    while (p1 >= 0 || p2 >= 0) {
        if (p1 == -1) {
            cur = nums2[p2--];
        } else if (p2 == -1) {
            cur = nums1[p1--];
        } else if (nums1[p1] > nums2[p2]) {
            cur = nums1[p1--];
        } else {
            cur = nums2[p2--];
        }
        nums1[tail--] = cur;
    }
}

Posted on Edited on In

83.Remove Duplicates from Sorted List

Example 1:

img

1
2
Input: head = [1,1,2]
Output: [1,2]

Example 2:

img

1
2
Input: head = [1,1,2,3,3]
Output: [1,2,3]

个人解答：

双指针

时间复杂度：O(n)

空间复杂度：O(1)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
ListNode* deleteDuplicates(ListNode* head) {
    if (!head) {
        return head;
    }
    ListNode* node1 = head;
    ListNode* node2 = head->next;
    while (node2 != nullptr) {
        if (node2->val == node1->val) {
            node1->next = node2->next;
            node2 = node2->next;
        }
        else {
            node1 = node1->next;
            node2 = node2->next;
        }
    }
    return head;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public:
    ListNode* deleteDuplicates(ListNode* head) {
        if (!head) {
            return head;
        }

        ListNode* cur = head;
        while (cur->next) {
            if (cur->val == cur->next->val) {
                cur->next = cur->next->next;
            }
            else {
                cur = cur->next;
            }
        }

        return head;
    }
};