leetcode Question: Binary Tree Paths

Binary Tree Paths

Given a binary tree, return all root-to-leaf paths.
For example, given the following binary tree:
   1
 /   \
2     3
 \
  5
All root-to-leaf paths are:


["1->2->5", "1->3"]

Analysis:


This is a classic depth first search problem.
The idea is

  1. Starting from the root node (remember to check NULL)
  2. Add current node into path (a string in function parameter) 
  3. Check if the current node is a leaf node: if yes, then save path
  4. Keep searching the left and right child of current node.



Code(C++):


/**
 * 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:
    void dfs(TreeNode* root, string str, vector<string> &res){
        if (!root){
           return;
        }else{
            if (str == ""){
                str += to_string(root->val);
            }else{
                str = str + "->" + to_string(root->val);    
            }
            if (!root->right && !root->left){
                if (str!=""){
                    res.push_back(str);
                }
            }
            dfs(root->left, str,res);
            dfs(root->right, str,res);
        }
    }
    vector<string> binaryTreePaths(TreeNode* root) {
        string str = "";
        vector<string> res;
        dfs(root,str,res);
        return res;
    }
};

Code(Python):


# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
    def dfs(self, root, s, res):
        if not root:
            return
        else:
            if s == "":
                s += str(root.val)
            else:
                s = s + "->" + str(root.val)
            if not root.right and not root.left:
                if s != "":
                    res.append(s)
            self.dfs(root.right,s,res)
            self.dfs(root.left,s,res)
    
    # @param {TreeNode} root
    # @return {string[]}
    def binaryTreePaths(self, root):
        res = []
        s = ""
        self.dfs(root, s, res)
        return res

leetcode Question: Product of Array Except Self

Product of Array Except Self

Given an array of n integers where n > 1, nums, return an array output such that output[i] is equal to the product of all the elements of nums except nums[i].
Solve it without division and in O(n).
For example, given [1,2,3,4], return [24,12,8,6].
Follow up:
Could you solve it with constant space complexity? (Note: The output array does not count as extra space for the purpose of space complexity analysis.)

Analysis:


This question has three requirements:

  • no division
  • O(n) time complexity
  • O(1) space complexity 

First let's only consider the time complexity O(n).

What can be done within O(n) time?

  • Scan the whole array once (often from the start to the end).

What about scan the array again?

  • Yes. It is still O(n) time ( \(O(2n) = O(n)\) ).
What about scan n times?

  • No. It is \(O(n*n)=O(n^2)\)

From the question above, we know that, at least we could scan the array twice (or other countable number if needed.).

OK, let's scan the array from start to end, e.g., [1,2,3,4].
The accumulated products can then be saved:
P_forward = [1,1*2, 1*2*3, 1*2*3*4] = [1, 2, 6, 24]


Let's get back to the problem, we need to get the product of all nums without current position, intuitively:
nums = [1, 2, 3, 4], for position 2 where nums[2] = 3, the product we want to have can be viewed:

  • left = 1*2
  • right  = 4
  • p = left * right

We already have the accumulated product from our first scanning, P_forward = [1, 2, 6, 24], which means, P_forward[i] = product from 0 to i. What about the product from i+1 to end?

The backward product is computed by scanning the array backward:
P_backward = [4, 12, 24, 24]

Note that, these products include the current element, so by adding a "1" in front of the product arrays will do fine:
P_forward =    [1, 1,  2,   6,  24]
P_backward = [1, 4, 12, 24, 24]

then, the final results can be easily computed:
res[0] = P_forward[0] * P_backward[3] = 24     (product before [0] * product from last to [1])
res[1] = P_forward[1] * P_backward[2] = 12     (product before [1] * product from last to [2])
res[2] = P_forward[2] * P_backward[1] = 8
res[3] = P_forward[3] * P_backward[0] = 6

res = [24, 12, 8, 6]


Now the problem is solved but:
  • O(1) space complexity 
If you check it carefully,

  • P_forward can be stored in the output array 
  • P_backward is actually not necessary, each time we compute one value, multiply it to correct P_forward, then the P_backward value can be overwritten for the next computation. 
Therefore, we have one output array of length n (which is not count as extra space as in the question description), one int for P_backward, one int for loop. It is O(1)!



Code(C++):

class Solution {
public:
    vector<int> productExceptSelf(vector<int>& nums) {
        vector<int> res(1,1);
        for (int i=0;i<nums.size();i++){
            res.push_back(res.back()*nums[i]);
        }
        int b = 1;
        for (int i=0;i<nums.size();i++){
            res[nums.size()-i-1] = res[nums.size()-i-1] * b;
            b = b* nums[nums.size()-i-1];
        }
        res.pop_back();
        return res;
    }
};


Code(Python):

class Solution(object):
    def productExceptSelf(self, nums):
        """
        :type nums: List[int]
        :rtype: List[int]
        """
        res = [1]
        for num in nums:
            res.append(res[-1]*num)
        b = 1   
        for i in range(len(nums)):
            res[len(nums)-i-1] = res[len(nums)-i-1] * b
            b = b* nums[len(nums)-i-1]
            
        return res[0:-1]
        
        




leetcode Question:Delete Node in a Linked List

Delete Node in a Linked List

Write a function to delete a node (except the tail) in a singly linked list, given only access to that node.
Supposed the linked list is 1 -> 2 -> 3 -> 4 and you are given the third node with value 3, the linked list should become 1 -> 2 -> 4 after calling your function.

Analysis:


To solve this problem, the key point is "overwrite" !

Usually we are thinking "skip" the node we want to delete by:
1 -> 2 -> 3 -> 4 -> Null, delete 3, we have:
1 -> 2--------> 4 -> Null.

However in this problem, the previous node is unknown.
So, what we should do is to overwrite the node  "3" by node "4":
1 -> 2 -> 3 -> 4->Null, delete 3, we have:
1 -> 2 -> 4->Null.

Just pay attention to the case that the node is the last node.


Code(C++):


/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    void deleteNode(ListNode* node) {
        if (node->next){
            node->val = node->next->val;
            node->next = node->next->next;
        }else{
            node = NULL;
        }
    }
};

Code(Python):


# Definition for singly-linked list.
# class ListNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution(object):
    def deleteNode(self, node):
        """
        :type node: ListNode
        :rtype: void Do not return anything, modify node in-place instead.
        """
        if node.next:
            node.val = node.next.val
            node.next = node.next.next
        else:
            node = None

leetcode Question: Lowest Common Ancestor of a Binary Tree

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 v and w as the lowest node in T that has both v and w as descendants (where we allow a node to be a descendant of itself).”
        _______3______
       /              \
    ___5__          ___1__
   /      \        /      \
   6      _2       0       8
         /  \
         7   4
For example, the lowest common ancestor (LCA) of nodes 5 and 1 is 3. Another example is LCA of nodes 5 and 4 is 5, since a node can be a descendant of itself according to the LCA definition.






The solution of this question is same as here.

leetcode Question: Lowest Common Ancestor of a Binary Search Tree

 Lowest Common Ancestor of a Binary Search Tree

Given a binary search tree (BST), find the lowest common ancestor (LCA) of two given nodes in the BST.
According to the definition of LCA on Wikipedia: “The lowest common ancestor is defined between two nodes v and w as the lowest node in T that has both v and w as descendants (where we allow a node to be a descendant of itself).”
        _______6______
       /              \
    ___2__          ___8__
   /      \        /      \
   0      _4       7       9
         /  \
         3   5
For example, the lowest common ancestor (LCA) of nodes 2 and 8 is 6. Another example is LCA of nodes 2 and 4 is 2, since a node can be a descendant of itself according to the LCA definition.

Analysis:


One obvious way to solve this problem is to utilizing the properties of Binary Search Tree:

  • It is ordered when you do Tree traversal
However, in this post, we are solving this problem in a more general way. (It is same as the problem here).

The idea is simple: recursion.

Usually when I do recursion problem, I consider:

  • What are we looking for?
  • What is the termination condition?
  • Which direction do we go for the searching?
According to this problem:
  • We are looking for the common ancestor. In other words, if the two node are in the current node's left and right child, respectively, current node is thus the lowest common ancestor.
  • When do we stop search? 1. Null node. 2. meet either one of the two nodes, the ancestor is this node or above.
  • Which direction do we go ? For a binary tree, left and right.  
So, we start the search from the root node, recursively find the common ancestor for root->left and root->right, if both of them are existed, which means root is the lowest common ancestor, otherwise, the existed one is the result.



Code(C++):

/**
 * 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){
            return NULL;
        }
        if (root == p || root == q){
            return root;
        }else{
            TreeNode* lc = lowestCommonAncestor(root->left, p, q);
            TreeNode* rc = lowestCommonAncestor(root->right, p, q);
            if (lc && rc){
                return root;
            }else{
                if (lc){return lc;}
                if (rc){return rc;}
            }
        }
    }
};

Code(Python):


# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution(object):
    def lowestCommonAncestor(self, root, p, q):
        """
        :type root: TreeNode
        :type p: TreeNode
        :type q: TreeNode
        :rtype: TreeNode
        """
        if not root:
            return None
        if root == p or root == q:
            return root
        else:
            lc = self.lowestCommonAncestor(root.left, p, q)
            rc = self.lowestCommonAncestor(root.right, p, q)
            if lc and rc:
                return root
            else:
                if lc:
                    return lc
                if rc:
                    return rc