Today we did trees and prefix sum. We learnt about how to think recursively and how to identify a prefix sum question.
Here are the questions
sum of all odd length subarrays
symmetric tree
Todays Prefix sum - ( https://leetcode.com/problems/sum-of-all-odd-length-subarrays )
public class Solution {
public int SumOddLengthSubarrays(int[] arr) {
int[] ps = new int[arr.Length+1];
ps[0] = 0;
for (int i=1;i<=arr.Length; i++)
ps[i] = ps[i-1] + arr[i-1];
int sum = 0;
for (int i=0; i<arr.Length; i++)
for (int j=i+1; j<=arr.Length; j=j+2)
{
sum += ps[j] - ps[i];
}
return sum;
}
}
Trees (LeetCode - The World's Leading Online Programming Learning Platform )
public class Solution {
public bool IsSymmetric(TreeNode root) {
if (root == null) return true;
return IsMirror(root.left, root.right);
}
private bool IsMirror(TreeNode t0, TreeNode t1 )
{
if (t0 == null && t1 == null) return true;
if (t0 == null || t1 == null) return false;
return (t0.val == t1.val &&
IsMirror(t0.left, t1.right) &&
IsMirror(t0.right, t1.left));
}
}
Today’s tree question:
/**
Definition for a binary tree node.
public class TreeNode {
public int val;
public TreeNode left;
public TreeNode right;
public TreeNode(int val=0, TreeNode left=null, TreeNode right=null) {
this.val = val;
this.left = left;
this.right = right;
}
}
*/
public class Solution {
public bool IsSymmetric(TreeNode root) {
if (root == null)
{
return true;
}
return Helper(root.left, root.right);
}
private bool Helper(TreeNode left, TreeNode right) {
if (left == null) {
return right == null;
}
if (right == null) {
return left == null;
}
if (left.val != right.val) {
return false;
}
if (Helper(left.left, right.right)) {
return Helper(left.right, right.left);
}
return false;
}
}
public class Solution {
public bool IsSymmetric(TreeNode root) {
if (root == null) return true;
return IsMirror(root.left, root.right);
}
private bool IsMirror(TreeNode t0, TreeNode t1 )
{
if (t0 == null && t1 == null) return true;
if (t0 == null || t1 == null) return false;
return (t0.val == t1.val &&
IsMirror(t0.left, t1.right) &&
IsMirror(t0.right, t1.left));
}
}