LeetCode – Page 9

Solution to Flatten Binary Tree to Linked List by LeetCode

6 Jul

Question: https://oj.leetcode.com/problems/flatten-binary-tree-to-linked-list/ Question Name: Flatten Binary Tree to Linked List The recursive method is easy to understand.

# Definition for a binary tree node

# class TreeNode:

# def __init__(self, x):

# self.val = x

# self.left = None

# self.right = None

class Solution:

# @param root, a tree node

# @return root, a tree node

def flattenHelper(self, root):

if root == None:

return None

else:

left = root.left

right = root.right

root.left = None # Truncate the left subtree

current = root

# Flatten the left subtree

current.right = self.flattenHelper(left)

while current.right != None: current = current.right

# Flatten the right subtree

current.right = self.flattenHelper(right)

return root

# @param root, a tree node

# @return nothing, do it in place

def flatten(self, root):

self.flattenHelper(root)

return

The iterative solution should be more efficient.

# Definition for a binary tree node

# class TreeNode:

# def __init__(self, x):

# self.val = x

# self.left = None

# self.right = None

class Solution:

# @param root, a tree node

# @return nothing, do it in place

def flatten(self, root):

if root == None: return

stack = [root.right, root.left]

current = root

while len(stack) != 0:

nextNode = stack.pop()

if nextNode == None:

continue

else:

# Truncate the left subtree

current.left = None

current.right = nextNode

current = current.right

stack.append(current.right)

stack.append(current.left)

return

Solution to Path Sum II by LeetCode

6 Jul

Question: https://oj.leetcode.com/problems/path-sum-ii/ Question Name: Path Sum II

# Definition for a binary tree node

# class TreeNode:

# def __init__(self, x):

# self.val = x

# self.left = None

# self.right = None

class Solution:

# @param root, a tree node

# @param sum, an integer

# @return a boolean

def pathSum(self, root, sum):

if root == None:

# Empty tree will always result in False

return []

elif root.left == None and root.right == None:

# Reach the leaf.

if root.val == sum: return [[root.val]]

else: return []

elif root.left == None:

# Only has right child.

result = self.pathSum(root.right, sum-root.val)

return [[root.val] + item for item in result]

elif root.right == None:

# Only has left child.

result = self.pathSum(root.left, sum-root.val)

return [[root.val] + item for item in result]

else:

# Has two children.

result = self.pathSum(root.left, sum-root.val)

result.extend(self.pathSum(root.right, sum-root.val))

return [[root.val] + item for item in result]

Solution to Path Sum by LeetCode

6 Jul

Question: https://oj.leetcode.com/problems/path-sum/ Question Name: Path Sum

# Definition for a binary tree node

# class TreeNode:

# def __init__(self, x):

# self.val = x

# self.left = None

# self.right = None

class Solution:

# @param root, a tree node

# @param sum, an integer

# @return a boolean

def hasPathSum(self, root, sum):

if root == None:

# Empty tree will always result in False

return False

elif root.left == None and root.right == None:

# Reach the leaf.

return root.val == sum

elif root.left == None:

# Only has right child.

return self.hasPathSum(root.right, sum-root.val)

elif root.right == None:

# Only has left child.

return self.hasPathSum(root.left, sum-root.val)

else:

# Has two children.

return self.hasPathSum(root.left, sum-root.val) or

self.hasPathSum(root.right, sum-root.val)

Solution to Minimum Depth of Binary Tree by LeetCode

5 Jul

Question: https://oj.leetcode.com/problems/minimum-depth-of-binary-tree/ Question Name: Minimum Depth of Binary Tree

# Definition for a binary tree node

# class TreeNode:

# def __init__(self, x):

# self.val = x

# self.left = None

# self.right = None

class Solution:

# @param root, a tree node

# @return an integer

def minDepth(self, root):

if root == None:

# This is an empty tree.

return 0

elif root.left == None and root.right == None:

# This is a leaf.

return 1

elif root.left == None:

# This non-leaf node only has right son.

return 1 + self.minDepth(root.right)

elif root.right == None:

# This non-leaf node only has left son.

return 1 + self.minDepth(root.left)

else:

# This non-leaf node has both left son and right son.

return 1 + min(self.minDepth(root.left),

self.minDepth(root.right))

Solution to Balanced Binary Tree by LeetCode

5 Jul

Question: https://oj.leetcode.com/problems/balanced-binary-tree/ Question Name: Balanced Binary Tree

# Definition for a binary tree node

# class TreeNode:

# def __init__(self, x):

# self.val = x

# self.left = None

# self.right = None

class Solution:

# @param root, a tree node

# @return a tuple, to say result. result[0] indicates whether the

# subtree, with "current" being the root, is balanced.

# result[1] is -1 if the substree is not balanced, or

# otherwise the height of this subtree.

def isBalancedHelper(self, current):

if current == None:

return (True, 0)

else:

# Check its left subtree

left = self.isBalancedHelper(current.left)

if left[0] == False:

return (False, -1)

# Check its right subtree

right = self.isBalancedHelper(current.right)

if right[0] == False:

return (False, -1)

# Check whether the depth of the two subtrees differ by

# more than 1.

if abs(left[1] - right[1]) <= 1:

height = max(left[1], right[1]) + 1

return (True, height)

else:

return (False, -1)

# @param root, a tree node

# @return a boolean

def isBalanced(self, root):

return self.isBalancedHelper(root)[0]

Solution to Convert Sorted List to Binary Search Tree by LeetCode

5 Jul

Question: https://oj.leetcode.com/problems/convert-sorted-list-to-binary-search-tree/ Question Name: Convert Sorted List to Binary Search Tree

# Definition for a binary tree node

# class TreeNode:

# def __init__(self, x):

# self.val = x

# self.left = None

# self.right = None

# Definition for singly-linked list.

# class ListNode:

# def __init__(self, x):

# self.val = x

# self.next = None

class Solution:

# @param num, a list of integers

# @return a tree node

def sortedArrayToBST(self, num):

''' With a given array num, the root of the corresponding tree

is always the middle one in the array.

'''

treeSize = len(num)

if treeSize == 0:

return None

else:

root = TreeNode(num[treeSize//2])

root.left = self.sortedArrayToBST(num[:treeSize//2])

root.right = self.sortedArrayToBST(num[treeSize//2+1:])

return root

# @param head, a list node

# @return a tree node

def sortedListToBST(self, head):

''' Firstly we convert the list into an array.

Then we construct the BST with that array.

'''

num = []

current = head

while current != None:

num.append(current.val)

current = current.next

return self.sortedArrayToBST(num)

Solution to Convert Sorted Array to Binary Search Tree by LeetCode

5 Jul

Question: https://oj.leetcode.com/problems/convert-sorted-array-to-binary-search-tree/ Question Name: Convert Sorted Array to Binary Search Tree

# Definition for a binary tree node

# class TreeNode:

# def __init__(self, x):

# self.val = x

# self.left = None

# self.right = None

class Solution:

# @param num, a list of integers

# @return a tree node

def sortedArrayToBST(self, num):

''' With a given array num, the root of the corresponding tree

is always the middle one in the array.

'''

treeSize = len(num)

if treeSize == 0:

return None

else:

root = TreeNode(num[treeSize//2])

root.left = self.sortedArrayToBST(num[:treeSize//2])

root.right = self.sortedArrayToBST(num[treeSize//2+1:])

return root

Solution to Binary Tree Level Order Traversal II by LeetCode

5 Jul

Question: https://oj.leetcode.com/problems/binary-tree-level-order-traversal-ii/ Question Name: Binary Tree Level Order Traversal II Nearly the same as the Binary Tree Level Order Traversal. We only need to reverse the output.

# Definition for a binary tree node

# class TreeNode:

# def __init__(self, x):

# self.val = x

# self.left = None

# self.right = None

class Solution:

# @param root, a tree node

# @return a list of lists of integers

def levelOrderBottom(self, root):

if root == None: return []

# In the first stage, we store hte nodes (not their value).

result = []

nextLayer = [root]

while len(nextLayer) != 0:

result.append(nextLayer)

# Gather the nodes in the next deeper layer.

nextLayer = []

for father in result[-1]:

if father.left != None: nextLayer.append(father.left)

if father.right != None: nextLayer.append(father.right)

# In the second stage, we convert the nodes into their values.

result = [[node.val for node in layer] for layer in result]

return result[::-1]

Solution to Construct Binary Tree from Preorder and Inorder Traversal by LeetCode

5 Jul

Question: https://oj.leetcode.com/problems/construct-binary-tree-from-preorder-and-inorder-traversal/ Question Name: Construct Binary Tree from Preorder and Inorder Traversal

# Definition for a binary tree node

# class TreeNode:

# def __init__(self, x):

# self.val = x

# self.left = None

# self.right = None

class Solution:

# @param inorder, a list of integers

# @param inOrderZone, an array to limit the nodes for current subtree

# inOrderZone[0] is the beginning position of current subtree

# in inorder array. inOrderZone[1] is the end position.

# @param inPos, a dictionary with the position of each char in inorder.

# @param preorder, a list of integers

# @param preOrderZone, an array to limit the nodes for current subtree.

# Same as inOrderZone.

# @param prePos, a dictionary with the position of each char in preorder.

# @return a tree node

def buildTreeHelper(self, inorder, inOrderZone, inPos,

preorder, preOrderZone, prePos):

''' Built the tree recuisively. The first element in preOrderZone

will always be the root of current tree (or subtree).

'''

# Reach the leaf.

if inOrderZone[1] < inOrderZone[0] : return None

# Create the root node of current (sub)tree

# The root node is in some middle place among inOrderZone.

# The root node is in the first position of current preOrderZone.

root = TreeNode(preorder[preOrderZone[0]])

# Recursively build the left son of current root

leftInOrderZone = [inOrderZone[0], inPos[root.val]-1]

leftCount = inPos[root.val] - inOrderZone[0]

leftPreOrderZone = [preOrderZone[0]+1, preOrderZone[0]+leftCount]

root.left = self.buildTreeHelper(inorder, leftInOrderZone, inPos,

preorder, leftPreOrderZone, prePos)

# Recursively build the right son of current root

rightInOrderZone = [inPos[root.val]+1, inOrderZone[1]]

rightCount = inOrderZone[1] - inPos[root.val]

rightPreOrderZone = [preOrderZone[1]-rightCount+1, preOrderZone[1]]

root.right = self.buildTreeHelper(inorder, rightInOrderZone, inPos,

preorder, rightPreOrderZone, prePos)

return root

# @param inorder, a list of integers

# @param preorder, a list of integers

# @return a tree node

def buildTree(self, preorder, inorder):

# There is not duplicate in the tree. And we record the position for

# each charater in the inorder array and preorder array.

inPos = {}

prePos = {}

for index in xrange(len(inorder)):

inPos[inorder[index]] = index

prePos[preorder[index]] = index

return self.buildTreeHelper(inorder, [0, len(inorder)-1], inPos,

preorder, [0, len(preorder)-1], prePos)

Solution to Construct Binary Tree from Inorder and Postorder Traversal by LeetCode

5 Jul

Question: https://oj.leetcode.com/problems/construct-binary-tree-from-inorder-and-postorder-traversal/ Question Name: Construct Binary Tree from Inorder and Postorder Traversal

# Definition for a binary tree node

# class TreeNode:

# def __init__(self, x):

# self.val = x

# self.left = None

# self.right = None

class Solution:

# @param inorder, a list of integers

# @param inOrderZone, an array to limit the nodes for current subtree

# inOrderZone[0] is the beginning position of current subtree

# in inorder array. inOrderZone[1] is the end position.

# @param inPos, a dictionary with the position of each char in inorder.

# @param postorder, a list of integers

# @param postOrderZone, an array to limit the nodes for current subtree.

# Same as inOrderZone.

# @param postPos, a dictionary with the position of each char in postorder.

# @return a tree node

def buildTreeHelper(self, inorder, inOrderZone, inPos,

postorder, postOrderZone, postPos):

''' Built the tree recuisively. The last element in postOrderZone

array will always be the root of current tree (or subtree).

'''

# Reach the leaf.

if inOrderZone[1] < inOrderZone[0] : return None

# Create the root node of current (sub)tree

# The root node is in some middle place among inOrderZone.

# The root node is in the last position of current postOrderZone.

root = TreeNode(postorder[postOrderZone[1]])

# Recursively build the left son of current root

leftInOrderZone = [inOrderZone[0], inPos[root.val]-1]

leftCount = inPos[root.val] - inOrderZone[0]

leftPostOrderZone = [postOrderZone[0], postOrderZone[0]+leftCount-1]

root.left = self.buildTreeHelper(inorder, leftInOrderZone, inPos,

postorder, leftPostOrderZone, postPos)

# Recursively build the right son of current root

rightInOrderZone = [inPos[root.val]+1, inOrderZone[1]]

rightCount = inOrderZone[1] - inPos[root.val]

rightPostOrderZone = [postOrderZone[1]-rightCount, postOrderZone[1]-1]

root.right = self.buildTreeHelper(inorder, rightInOrderZone, inPos,

postorder, rightPostOrderZone, postPos)

return root

# @param inorder, a list of integers

# @param postorder, a list of integers

# @return a tree node

def buildTree(self, inorder, postorder):

# There is not duplicate in the tree. And we record the position for

# each charater in the inorder array and postorder array.

inPos = {}

postPos = {}

for index in xrange(len(inorder)):

inPos[inorder[index]] = index

postPos[postorder[index]] = index

return self.buildTreeHelper(inorder, [0, len(inorder)-1], inPos,

postorder, [0, len(postorder)-1], postPos)

tl;dr: Please put your code into a <pre>YOUR CODE</pre> section.

Hello everyone!

If you want to ask a question about the solution. DO READ the post and comments firstly.

If you had some troubles in debugging your solution, please try to ask for help on StackOverflow, instead of here.

If you want to post some comments with code or symbol, here is the guidline.

1. To post your code, please add the code inside a <pre> </pre> section (preferred), or <code> </code>. And inside the pre or code section, you do not need to escape < > and &, e.g. no need to use < instead of <.

2. To use special symbols < and > outside the pre block, please use "<" and ">" instead.

3. If you have a comment with lots of < and >, you could add the major part of your comment into a <pre class="decode:true crayon-inline "> YOUR COMMENTS </pre> section.

Finally, if you are posting the first comment here, it usually needs moderation. Please be patient and stay tuned. Thanks!

CodeSays.com Admin

Ovi February 12, 2024 at 11:14 pm on Solution to Min-Perimeter-Rectangle by codilityExactly my question too. I tried something very similar to Sheng's solution, importing the math module and using sqrt(). Codility marked it only as 80%,...
Doron Ben Ari February 11, 2024 at 4:10 am on Solution to Min-Avg-Two-Slice by codilityInspired by Sheng's great solution, I wrote the following proof: Assume you found the slice with minimal average. Assume the first two consecutive elements of...
Ovi February 4, 2024 at 9:03 am on Solution to sigma2012 (Stone-Wall) by codility def solution(H): heights = H # geometric logic: the blocks need to be cuboid, all sides are rectagular. Nothing fancy, means that the angles...
Ovidiu Oprea February 2, 2024 at 11:06 am on Solution to Fish by codilityIt's the reason why it took me 2 weeks to finish this task (in the context of adult life with non-dev job). I was trying...
Ovi January 15, 2024 at 2:40 pm on Solution to Brackets by codilityThanks for this blog post! I was banging my head against the wall thinking this is a simple / short solution, where you just build...
parikshit verma July 5, 2023 at 8:26 am on Solution to Missing-Integer by codility def missingnum(a): st=min(a) en=max(a) b=set(range(1,en+2)) if (en<1 or st>1) : return 1 else: return min(b-set(a))
Pavankumar Nandeshwar June 26, 2023 at 8:07 am on Solution to Dwarfs-Rafting by codilityOk fixed it. gives 100%: int solution(int N, string &S, string &T) { int q = N / 2 * N / 2; int lf...
Pavankumar Nandeshwar June 26, 2023 at 5:23 am on Solution to Dwarfs-Rafting by codilityCan someone explain what is wrong with my solution in C++ ? int solution(int N, string &S, string &T) { int q = N /...
Pavankumar Nandeshwar June 23, 2023 at 10:25 pm on Solution to Flood-Depth by codilityMy C++ Solution. O(N) #include <climits> int solution(vector<int> &A) { int max_depth {}; int max_lvl = {}; int min_lvl = INT_MAX; for (unsigned int i...