My Own Notes
Tuesday, September 30, 2014
Sunday, September 14, 2014
Leetcode (Python): Populating Next Right Pointers in Each Node II
Follow up for problem "Populating Next Right Pointers in Each Node".
What if the given tree could be any binary tree? Would your previous solution still work?
Note:
- You may only use constant extra space.
For example,
Given the following binary tree,
Given the following binary tree,
1
/ \
2 3
/ \ \
4 5 7
After calling your function, the tree should look like:
1 -> NULL
/ \
2 -> 3 -> NULL
/ \ \
4-> 5 -> 7 -> NULL
Solution:
# Definition for a binary tree node # class TreeNode: # def __init__(self, x): # self.val = x # self.left = None # self.right = None # self.next = None class Solution: # @param root, a tree node # @return nothing def connect(self, root): firstNodeLevel = root while firstNodeLevel != None: firstNodeNextLevel = None tempNextLevel = None pointer = firstNodeLevel while pointer != None: if pointer.left != None: if firstNodeNextLevel == None: firstNodeNextLevel = pointer.left else: tempNextLevel.next = pointer.left tempNextLevel = pointer.left if pointer.right != None: if firstNodeNextLevel == None: firstNodeNextLevel = pointer.right else: tempNextLevel.next = pointer.right tempNextLevel = pointer.right pointer = pointer.next firstNodeLevel = firstNodeNextLevel
Leetcode (Python): Valid Palindrome
Given a string, determine if it is a palindrome, considering only alphanumeric characters and ignoring cases.
For example,
"A man, a plan, a canal: Panama"
is a palindrome."race a car"
is not a palindrome.
Note:
Have you consider that the string might be empty? This is a good question to ask during an interview.
Have you consider that the string might be empty? This is a good question to ask during an interview.
For the purpose of this problem, we define empty string as valid palindrome.
Solution:
class Solution: # @param s, a string # @return a boolean def isPalindrome(self, s): start = 0; end = len(s)-1 while start<end: while start<end and not s[start].isalnum(): start +=1 while start<end and not s[end].isalnum(): end -=1 if start<end and s[start].lower() != s[end].lower(): return False start +=1 end -= 1 return True
Leetcode: Valid Palindrome
Given a string, determine if it is a palindrome, considering only alphanumeric characters and ignoring cases.
For example,
"A man, a plan, a canal: Panama"
is a palindrome."race a car"
is not a palindrome.
Note:
Have you consider that the string might be empty? This is a good question to ask during an interview.
Have you consider that the string might be empty? This is a good question to ask during an interview.
For the purpose of this problem, we define empty string as valid palindrome.
Solution:
public class Solution { public boolean isPalindrome(String s) { int start = 0; int end = s.length()-1; while(start<end) { while(start<end && ! Character.isLetterOrDigit(s.charAt(start))) start++; while(start<end && ! Character.isLetterOrDigit(s.charAt(end))) end--; if (start<end && Character.toLowerCase(s.charAt(start))!= Character.toLowerCase(s.charAt(end))) return false; start++; end--; } return true; } }
Leetcode (Python): Sum Root to Leaf Numbers
Given a binary tree containing digits from
0-9
only, each root-to-leaf path could represent a number.
An example is the root-to-leaf path
1->2->3
which represents the number 123
.
Find the total sum of all root-to-leaf numbers.
For example,
1
/ \
2 3
The root-to-leaf path
The root-to-leaf path
1->2
represents the number 12
.The root-to-leaf path
1->3
represents the number 13
.
Return the sum = 12 + 13 =
25
.Solution:
# 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 sumNumbers(self, root): self.sum = 0; self.sumNumbersRec(root,0) return self.sum def sumNumbersRec(self, root, partialSum): if root == None: return partialSum = partialSum *10 + root.val; if root.left == None and root.right == None: self.sum += partialSum else: self.sumNumbersRec(root.left, partialSum) self.sumNumbersRec(root.right, partialSum)
Leetcode: Sum Root to Leaf Numbers
Given a binary tree containing digits from
0-9
only, each root-to-leaf path could represent a number.
An example is the root-to-leaf path
1->2->3
which represents the number 123
.
Find the total sum of all root-to-leaf numbers.
For example,
1
/ \
2 3
The root-to-leaf path
The root-to-leaf path
1->2
represents the number 12
.The root-to-leaf path
1->3
represents the number 13
.
Return the sum = 12 + 13 =
25
.Solution:
/** * Definition for binary tree * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */ public class Solution { int sum; public int sumNumbers(TreeNode root) { sum = 0; sumNumbers(root, 0); return sum; } public void sumNumbers(TreeNode root, int partialSum) { if(root == null) return; partialSum = partialSum*10 + root.val; if (root.left==null && root.right == null) sum += partialSum; else { sumNumbers(root.left, partialSum); sumNumbers(root.right, partialSum); } } }
Saturday, September 13, 2014
Leetcode (Python): Binary Tree Preorder Traversal
Given a binary tree, return the preorder traversal of its nodes' values.
For example:
Given binary tree
Given binary tree
1 \ 2 / 3
return
[1,2,3]
.Solution:
# 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 integers def preorderTraversal(self, root): solution = [] stack = [] node = root while node != None or len(stack)>0: if node != None: solution.append(node.val) stack.append(node) node = node.left else: node = stack.pop().right return solution
Subscribe to:
Posts
(
Atom
)