Fork me on GitHub
image frame

Yangyang

Think. Learn. Create
Try to update hard.

Leetcode Study Day 41

Leetcode

Minimum Absolute Difference in BST

Given the root of a Binary Search Tree (BST), return the minimum absolute difference between the values of any two different nodes in the tree.

1
2
3
4
5
6
7
8
9
10
Example 1:


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


Input: root = [1,0,48,null,null,12,49]
Output: 1

My solution

My solution is to use breadth first search to store all the values of the nodes in the tree into a vector. Then we sort the vector. Then we use a for loop to find the minimum difference between the adjacent values in the vector. Then we return the minimum difference.

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
/**
 * 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 <int> numbers;
    int getMinimumDifference(TreeNode* root) {
        queue<TreeNode* > treeQ;
        treeQ.push(root);
        while(!treeQ.empty()){
            TreeNode* node = treeQ.front();
            treeQ.pop();
            numbers.push_back(node->val);
            if(node->left) treeQ.push(node->left);
            if(node->right) treeQ.push(node->right);
        }
        sort(numbers.begin(), numbers.end());
        int n = numbers.size();
        if(n == 1) return numbers[0];
        int minDif = INT_MAX;
        for(int i = 1; i < n; i++){
            minDif = min(numbers[i]-numbers[i-1], minDif);
        }
        return minDif;
    }
};

Kth Smallest Element in a BST

Given the root of a binary search tree, and an integer k, return the kth (1-indexed) smallest element in the tree.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
Example 1:


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


Input: root = [5,3,6,2,4,null,null,1], k = 3
Output: 3
 

Constraints:

The number of nodes in the tree is n.
1 <= k <= n <= 104
0 <= Node.val <= 104

My solution

(正所谓一招鲜吃遍天) As the saying goes, “one trick pays off”, I used the same method as the previous question. I used breadth first search to store all the values of the nodes in the tree into a vector. Then we sort the vector. Then we return the kth element in the vector.

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
/**
 * 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 <int> numbers;
    int kthSmallest(TreeNode* root, int k) {
        queue<TreeNode* > treeQ;
        treeQ.push(root);
        while(!treeQ.empty()){
            TreeNode* node = treeQ.front();
            treeQ.pop();
            numbers.push_back(node->val);
            if(node->left) treeQ.push(node->left);
            if(node->right) treeQ.push(node->right);
        }
        sort(numbers.begin(),numbers.end());
        return numbers[k-1];
    }
};

Improved method

Since my code use a queue ana a vector, which is memory consuming, I found a better solution.

The property of a Binary Search Tree (BST) that makes in-order traversal effective for this task is that in-order traversal of a BST yields the nodes in ascending order. This means that as I traverse the tree in in-order fashion, the first node I encounter is the smallest, the second node is the second smallest, and so on.

So remember, when meeting a binary search tree problem, we always first consider inorder traversal.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
public:
    int count = 0; // Counter for the number of processed nodes
    int result = -1; // Variable to store the kth smallest value

    void inOrder(TreeNode* node, int k) {
        if (node == nullptr || count >= k) return;
        
        inOrder(node->left, k); // Traverse the left subtree
        
        // Increment count and check if we've reached the kth smallest
        if (++count == k) {
            result = node->val; // Found kth smallest
            return;
        }
        
        inOrder(node->right, k); // Traverse the right subtree
    }

    int kthSmallest(TreeNode* root, int k) {
        inOrder(root, k);
        return result;
    }
};

Leetcode Study Day 40

Leetcode

Binary Tree Level Order Traversal

Given the root of a binary tree, return the level order traversal of its nodes’ values. (i.e., from left to right, level by level).

1
2
3
4
5
6
7
8
9
10
11
12
13
Example 1:


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

Input: root = [1]
Output: [[1]]
Example 3:

Input: root = []
Output: []

Solution

Like other breadth first search questions, we use a queue to store the nodes in the same level. We first push the root into the queue. Then we use a while loop to check if the queue is empty. If it is not empty, we get the size of the queue. The size of the queue is the number of nodes in the same level. We use a for loop to pop the nodes in the queue and add the value of the node to the sum. Then we check if the node has left child or right child. If it has, we push the child into the queue. After the for loop, we push the singleLevel vector into the answer vector. Then we return the answer vector.

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
/**
 * 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>> levelOrder(TreeNode* root) {
        vector<vector<int>> ans;
        queue<TreeNode*> treeQ;
        if (!root) return ans;
        treeQ.push(root);
        while(!treeQ.empty()){
            vector<int> singleLevel;
            int size = treeQ.size();
            for (int i = 0; i<size; i++){
                TreeNode* node = treeQ.front();
                treeQ.pop();
                if (node->left) treeQ.push(node->left);
                if (node->right) treeQ.push(node->right);
                singleLevel.push_back(node->val);
            }
            ans.push_back(singleLevel);

        }
        return ans;
    }
};

Binary Tree Zigzag Level Order Traversal

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).

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

My solution

This question’s solution is quite similar to the previous one, except for I adding a boolean variable to determine whether to reverse the single vector. If the boolean variable is true, we reverse the single vector. Then we push the single vector into the answer vector. Then we return the answer vector.

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
/**
 * 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>> zigzagLevelOrder(TreeNode* root) {
        vector<vector<int>> ans;
        queue <TreeNode*> treeQ;
        if(!root) return ans;
        treeQ.push(root);
        bool flag = false;
        while(!treeQ.empty()){
            int size = treeQ.size();
            vector <int> single;
            for(int i = 0; i < size; i++){
                TreeNode* node = treeQ.front();
                treeQ.pop();
                single.push_back(node->val);
                if(node->left) treeQ.push(node->left);
                if(node->right) treeQ.push(node->right);
            }
            if (flag) reverse(single.begin(),single.end());
            ans.push_back(single);
            flag = !flag;
        }
        return ans;
    }
};

Leetcode Study Day 39

Leetcode

Average of Levels in Binary Tree

Given the root of a binary tree, return the average value of the nodes on each level in the form of an array. Answers within 10-5 of the actual answer will be accepted.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
Example 1:


Input: root = [3,9,20,null,null,15,7]
Output: [3.00000,14.50000,11.00000]
Explanation: The average value of nodes on level 0 is 3, on level 1 is 14.5, and on level 2 is 11.
Hence return [3, 14.5, 11].
Example 2:


Input: root = [3,9,20,15,7]
Output: [3.00000,14.50000,11.00000]
 

Constraints:

The number of nodes in the tree is in the range [1, 104].
-231 <= Node.val <= 231 - 1

Solution

To solve a breadth first search question, we use a queue. Queue’s feature is first in first out. So we can use it to store the nodes in the same level. We first push the root into the queue. Then we use a while loop to check if the queue is empty. If it is not empty, we get the size of the queue. The size of the queue is the number of nodes in the same level. We use a for loop to pop the nodes in the queue and add the value of the node to the sum. Then we check if the node has left child or right child. If it has, we push the child into the queue. After the for loop, we push the average of the sum and the size into the answer vector. Then we return the answer vector.

It is noticible that to convert int to double, we can firstly use (double) add an int, then the result will be double.

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
/**
 * 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<double> averageOfLevels(TreeNode* root) {
        vector<double> ans;
        queue<TreeNode*> treeQ;
        if(!root) return ans;
        treeQ.push(root);
        while(!treeQ.empty()){
            int size = treeQ.size();
            long sum = 0;
            for(int i = 0; i < size; i++){
                TreeNode* node = treeQ.front();
                treeQ.pop();
                sum += node->val;
                if(node->left) treeQ.push(node->left);
                if(node->right) treeQ.push(node->right);
            }
            ans.push_back((double)sum/size);
        }
        return ans;
    }
};

Leetcode Study Day 39

Leetcode

Binary Tree Right Side View

Given the root of a binary tree, imagine yourself standing on the right side of it, return the values of the nodes you can see ordered from top to bottom.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
Example 1:


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

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

Input: root = []
Output: []
 

Constraints:

The number of nodes in the tree is in the range [0, 100].
-100 <= Node.val <= 100

Solution

The solution calls a function “recursion”. In this function, it will first check if the node is null. If it is null, it will return. If the size of the answer vector is smaller than the level, it will push the value of the node into the vector, which means it will check whether at this level of the tree, there is already has a node on the most right side (in the array). Then it will call the recursion function on the right subtree and left subtree. The order is right first and then left. The reason is that we want to push the node on the most right side into the vector first.

One thing to notice is that we should pass the address of the vector into the function (&ans). Otherwise, the vector will not be changed.

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
/**
 * 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:
    void recursion(TreeNode* node, int level, vector<int> &ans){
        if(!node) return;
        if(ans.size()<level)
            ans.push_back(node->val);
        recursion(node->right,level+1,ans);
        recursion(node->left,level+1,ans);
    }
    vector<int> rightSideView(TreeNode* root) {
        vector <int> ans;
        recursion(root,1,ans);
        return ans;
    }
};

Leetcode Study Day 38

Leetcode

Lowest Common Ancestor of a Binary Tree

Given a binary tree, find the lowest common ancestor (LCA) of two given nodes in the tree.

According to the definition of LCA on Wikipedia: “The lowest common ancestor is defined between two nodes p and q as the lowest node in T that has both p and q as descendants (where we allow a node to be a descendant of itself).”

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
Example 1:


Input: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 1
Output: 3
Explanation: The LCA of nodes 5 and 1 is 3.
Example 2:


Input: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 4
Output: 5
Explanation: The LCA of nodes 5 and 4 is 5, since a node can be a descendant of itself according to the LCA definition.
Example 3:

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

Constraints:

The number of nodes in the tree is in the range [2, 105].
-109 <= Node.val <= 109
All Node.val are unique.
p != q
p and q will exist in the tree.

Solution

The solution is not easy to understand, but it is neat and clean. We can divide the problem into three parts:

  1. If the root is null or the root is one of the two nodes, we return the root.
  2. We recursively call the function to find the lowest common ancestor of the left and right subtree.
  3. If the left and right subtree both return a node, it means the current root is the lowest common ancestor. If only one of them return a node, it means the lowest common ancestor is in the subtree. If both of them return null, it means the lowest common ancestor is not in the subtree.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        if(!root || root == p || root ==q)  return root;
        TreeNode * left = lowestCommonAncestor(root -> left, p, q);
        TreeNode * right = lowestCommonAncestor(root -> right, p, q);
        if(!left && !right) return nullptr;
        if(left && right) return root;
        return !left ? right: left;
    }
};

Leetcode Study Day 38

Leetcode

Count Complete Tree Nodes

Given the root of a complete binary tree, return the number of the nodes in the tree.

According to Wikipedia, every level, except possibly the last, is completely filled in a complete binary tree, and all nodes in the last level are as far left as possible. It can have between 1 and 2h nodes inclusive at the last level h.

Design an algorithm that runs in less than O(n) time complexity.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
Example 1:


Input: root = [1,2,3,4,5,6]
Output: 6
Example 2:

Input: root = []
Output: 0
Example 3:

Input: root = [1]
Output: 1
 

Constraints:

The number of nodes in the tree is in the range [0, 5 * 104].
0 <= Node.val <= 5 * 104
The tree is guaranteed to be complete.

Solution

We create two functions, countLeft and countRight to count the layer of left and right subtree. If they are equal, we can use the formula (number of nodes equals to 2**layer - 1) to calculate the number of nodes. Otherwise, we plus one and recursively call the function to count the number of nodes in the left and right subtree.

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
40
41
42
43
/**
 * 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 countLeft(TreeNode* node){
        if (!node)
            return 0;
        if (!node->left){
            return 1;
        }
        else
            return 1 + countLeft(node->left);
    }
    int countRight(TreeNode* node){
        if (!node)
            return 0;
        if (!node->right){
            return 1;
        }
        else
            return 1 + countRight(node->right);
    }

    int countNodes(TreeNode* root) {
        if(!root)
            return 0;
        int layerLeft = countLeft(root);
        int layerRight = countRight(root);
        if (layerLeft == layerRight)
            return pow(2,layerLeft) - 1;
        else
            return (1+countNodes(root->left)+countNodes(root->right));
    }
};

Leetcode Study Day 37

Leetcode

Binary Search Tree Iterator

Implement the BSTIterator class that represents an iterator over the in-order traversal of a binary search tree (BST):

BSTIterator(TreeNode root) Initializes an object of the BSTIterator class. The root of the BST is given as part of the constructor. The pointer should be initialized to a non-existent number smaller than any element in the BST.
boolean hasNext() Returns true if there exists a number in the traversal to the right of the pointer, otherwise returns false.
int next() Moves the pointer to the right, then returns the number at the pointer.
Notice that by initializing the pointer to a non-existent smallest number, the first call to next() will return the smallest element in the BST.

You may assume that next() calls will always be valid. That is, there will be at least a next number in the in-order traversal when next() is called.

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
Example 1:


Input
["BSTIterator", "next", "next", "hasNext", "next", "hasNext", "next", "hasNext", "next", "hasNext"]
[[[7, 3, 15, null, null, 9, 20]], [], [], [], [], [], [], [], [], []]
Output
[null, 3, 7, true, 9, true, 15, true, 20, false]

Explanation
BSTIterator bSTIterator = new BSTIterator([7, 3, 15, null, null, 9, 20]);
bSTIterator.next();    // return 3
bSTIterator.next();    // return 7
bSTIterator.hasNext(); // return True
bSTIterator.next();    // return 9
bSTIterator.hasNext(); // return True
bSTIterator.next();    // return 15
bSTIterator.hasNext(); // return True
bSTIterator.next();    // return 20
bSTIterator.hasNext(); // return False
 

Constraints:

The number of nodes in the tree is in the range [1, 105].
0 <= Node.val <= 106
At most 105 calls will be made to hasNext, and next.

My solution

My solution is first to use a recursive function to add the value of each node into the private array by inorder traversal. For next() function, I set a pointer to point to the current index of the array. For hasNext() function, I check if the pointer is equal to the size of the array. If it is, return false, otherwise return true.

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
40
41
42
43
44
45
46
47
48
49
50
/**
 * 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 BSTIterator {
public:
    void BSTArrayAdder (TreeNode* node){
        if(!node) return;
        if(!node->left && !node->right){
            BSTArray.push_back(node -> val);
            return;
        }
        BSTArrayAdder(node->left);
        BSTArray.push_back(node -> val);
        BSTArrayAdder(node->right);
    }

    BSTIterator(TreeNode* root) {
        BSTArrayAdder(root);
    }
    
    int next() {
        int next = BSTArray[count];
        count ++;
        return next;
    }
    
    bool hasNext() {
        if (count == BSTArray.size())
            return false;
        else return true;
    }
private:
    vector <int> BSTArray;
    int count = 0;
};

/**
 * Your BSTIterator object will be instantiated and called as such:
 * BSTIterator* obj = new BSTIterator(root);
 * int param_1 = obj->next();
 * bool param_2 = obj->hasNext();
 */

Leetcode Study Day 37

Leetcode

Binary Tree Maximum Path Sum

A path in a binary tree is a sequence of nodes where each pair of adjacent nodes in the sequence has an edge connecting them. A node can only appear in the sequence at most once. Note that the path does not need to pass through the root.

The path sum of a path is the sum of the node’s values in the path.

Given the root of a binary tree, return the maximum path sum of any non-empty path.

image

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
Example 1:


Input: root = [1,2,3]
Output: 6
Explanation: The optimal path is 2 -> 1 -> 3 with a path sum of 2 + 1 + 3 = 6.
Example 2:


Input: root = [-10,9,20,null,null,15,7]
Output: 42
Explanation: The optimal path is 15 -> 20 -> 7 with a path sum of 15 + 20 + 7 = 42.
 

Constraints:

The number of nodes in the tree is in the range [1, 3 * 104].
-1000 <= Node.val <= 1000

Solution

I found a detaild explanation from Leetcode

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
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
The way to think of a solution to this is that when we are looking a path in a tree its unidirectional and cannot retrace back what i mean by that is:
    _
  / 1 \ 
 / / \ \ <-----path that goes like a depth first search without backtracking
/ 2   3 v  

So a way to solve this is that if i am at a node i can choose a left or right subtree but if i choose both this is the only subtree that will contain my maximum

I first set my max_sum to INT_MIN.
I can do either either of the options presented:
1.I can choose to take up the left subtree or drop it.
2.I can either choose to take up the right subtree or drop it.
3.I check for a possibility whether if i were to take both left subtree and right subtree would that beat my current max_sum?
Lets consider
   -10
   / \
  9  20
    /  \
   15   7
I do my postorder traversal with a bit of variation:-

int l=max(max_gain(root->left),0);
int r=max(max_gain(root->right),0);
But why?
This is because I have the option to choose the left or right subtree or whether i will just settle with my root value.

So I do my regular postorder traversal and do the above steps
I hit 9

    9
   / \
NULL  NULL

int l=0,r=0(Base condition)
i store the value of 9+0+0 in a variable
Then check if this is greater than maxsum or not is so i update it.
As my max_sum was INT_MIN it gets updated to 9

Now we explore the right tree of root which reaches 15

    15
   / \
NULL  NULL

int l=0,r=0(Base condition)
i store the value of 9+0+0 in a variable
Then check if this is greater than maxsum or not is so i update it.
As my max_sum was 9 it gets updated to 15

Similarly with 7 but 7 doesnt beat the max_sum so nothing happens.

Now we backtrack 20
here int r=7(as 7>0)
     int l=15(as 15>0)
 now i check whether 20+15+7(considering this subtree to be my maximum)
 as 42>15 max_sum=42
 Now what if we dont consider this subtree?

 Then we choose 20 and maximum of its left or right subtree
 so we send return root->val+max(l,r) to our recursion stack
 so when i reach the root it would be like this
           -10
           /  \    <----I considered 15 and 20 because its along a path and is greater than 20+7
          9    35
  int l=9
      r=35
      check whether 9+35+-10=34 beats max_sum
      34<42 so nothing happens and we return -10+max(9,35)=25 to the caller after which we break out of the helper function and we get max_sum as 42.

Full code

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
/**
 * 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 maxSum = INT_MIN;
    int calculatePath(TreeNode* root){
        if (!root) return 0;
        int left = max(calculatePath(root -> left), 0);
        int right = max(calculatePath(root -> right), 0);
        maxSum = max(maxSum, root -> val + left +right);
        return root -> val + max(left, right);
    }

    int maxPathSum(TreeNode* root) {
        calculatePath(root);
        return maxSum;
    }
};

Leetcode Study Day 36

Leetcode

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.

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
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 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

Solution

I saw a very simple solution from Leetcode.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
/**
 * 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 the node is empty, return false
        if (!root)
            return false;
        // If it is the end of the tree and the value is equal to the sum passed in, return true
        if (root -> val == targetSum && !root -> left && !root -> right)
            return true;
        // If it is not the end of the tree, check the left and right node, with the sum minus the current value
        return (hasPathSum(root -> left, targetSum - root -> val) || hasPathSum(root -> right, targetSum - root -> val)); 
    }
};

Sum Root to Leaf Numbers

You are given the root of a binary tree containing digits from 0 to 9 only.

Each root-to-leaf path in the tree represents a number.

For example, the root-to-leaf path 1 -> 2 -> 3 represents the number 123.
Return the total sum of all root-to-leaf numbers. Test cases are generated so that the answer will fit in a 32-bit integer.

A leaf node is a node with no children.

Example 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
Example 1:


Input: root = [1,2,3]
Output: 25
Explanation:
The root-to-leaf path 1->2 represents the number 12.
The root-to-leaf path 1->3 represents the number 13.
Therefore, sum = 12 + 13 = 25.
Example 2:


Input: root = [4,9,0,5,1]
Output: 1026
Explanation:
The root-to-leaf path 4->9->5 represents the number 495.
The root-to-leaf path 4->9->1 represents the number 491.
The root-to-leaf path 4->0 represents the number 40.
Therefore, sum = 495 + 491 + 40 = 1026.
 

Constraints:

The number of nodes in the tree is in the range [1, 1000].
0 <= Node.val <= 9
The depth of the tree will not exceed 10.

My solution

I found that for each layer, the number of that path is 10 times the last layer. For example, for node 9, it represents for 49, which equals 4 (the previous node) * 10 + 9 (the current node). Based on this idea, I wrote the following code.

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
/**
 * 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 sumPath(TreeNode* node, int sum){
        if (!node)  return 0;
        // the end of the tree
        if(node && !node -> left && !node->right){
            return sum = 10 * sum + node -> val;
        }
        sum = 10 * sum + node->val;
        return sum = sumPath(node->left, sum)+ sumPath(node->right,sum);
    }

    int sumNumbers(TreeNode* root) {
        if(!root) return NULL;
        return sumPath(root, 0);
    }
};

Leetcode Study Day 35

Leetcode

Flatten Binary Tree to Linked List

Given the root of a binary tree, flatten the tree into a “linked list”:

The “linked list” should use the same TreeNode class where the right child pointer points to the next node in the list and the left child pointer is always null.
The “linked list” should be in the same order as a pre-order traversal of the binary tree.

1
2
3
4
5
6
7
8
9
10
11
12
13
Example 1:


Input: root = [1,2,5,3,4,null,6]
Output: [1,null,2,null,3,null,4,null,5,null,6]
Example 2:

Input: root = []
Output: []
Example 3:

Input: root = [0]
Output: [0]

Solution

I found this smart solution from Leetcode.

Full code

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
/**
 * 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:
    void flatten(TreeNode* root) {
        // if current node is not empty
        if(root){
            // store right node, and move left to right
            TreeNode *temp = root -> right;
            root -> right = root -> left;
            // set left to nullptr
            root -> left = nullptr;
            // find the end of right node
            TreeNode *currentNode = root;
            while(currentNode -> right)
                currentNode = currentNode -> right;
            // Connect temp at the end of right node
            currentNode -> right = temp;
            // mvoe to the next right node
            flatten(root->right);
        }
        return;
    }
};

Understand

To understand this method better, I asked ChatGPT to draw a procedure diagram for me. Here is the result:

Given the input binary tree root = [1,2,5,3,4,null,6], the tree structure would initially look like this:

1
2
3
4
5
    1
   / \
  2   5
 / \   \
3   4   6

Here’s how the flatten function would process this tree step-by-step:

Initial call with root (node 1):

Moves left (node 2) to right.
Sets left to nullptr.
Now the tree looks like this:

1
2
3
4
5
1
 \
  2
 / \
3   4

Then we add the right subtree (node 5) to the end of the rightmost branch:

1
2
3
4
5
6
7
8
9
1
 \
  2
 / \
3   4
     \
      5
       \
        6

Then we call flatten on the right subtree (node 2), we move left (node 3) to right and move the other nodes to the right child of node 3.

1
2
3
4
5
6
7
8
9
10
11
1
 \
  2
   \
    3
     \
      4
       \
        5
         \
          6

Then we find that actually, all the nodes are at the right side, however, the function will continue running, like put the temp(node 5) connect to the end of the node 4, but the result will still be the same.

  • Copyrights © 2020-2024 Yangyang Cui

请我喝杯咖啡吧~

支付宝
微信