LeetCode: Same Tree

Given two binary trees, write a function to check if they are equal or not.

Two binary trees are considered equal if they are structurally identical and the nodes have the same value.

 /**  
  * Definition for binary tree  
  * struct TreeNode {  
  *   int val;  
  *   TreeNode *left;  
  *   TreeNode *right;  
  *   TreeNode(int x) : val(x), left(NULL), right(NULL) {}  
  * };  
  */  

   bool isSameTree(TreeNode *p, TreeNode *q) {  
     if(!p && !q)return true;  
     if(!p || !q)return false;  
     return ((p->val == q->val) && isSameTree(p->left,q->left) && isSameTree(p->right,q->right) );  
   }  

LeetCode: Symmetric Tree

Given a binary tree, check whether it is a mirror of itself (ie, symmetric around its center).

For example, this binary tree is symmetric:

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

But the following is not:

    1
   / \
  2   2
   \   \
   3    3

Note:
Bonus points if you could solve it both recursively and iteratively.

confused what "{1,#,2,3}" means? > read more on how binary tree is serialized on OJ.

 /**  
  * Definition for binary tree  
  * struct TreeNode {  
  *   int val;  
  *   TreeNode *left;  
  *   TreeNode *right;  
  *   TreeNode(int x) : val(x), left(NULL), right(NULL) {}  
  * };  
  */ 

 
   bool isMirror(TreeNode *root1, TreeNode *root2)  
   {  
     if(!root1 && !root2)return true;  
     if(!root1 || !root2)return false;  
     return (root1->val==root2->val && isMirror(root1->left, root2->right) && isMirror(root1->right, root2->left));  
   }  

   bool isSymmetric(TreeNode *root) {  
     if(!root)return true;  
     if(!root->left && !root->right)return true;  
     return isMirror(root->left, root->right);  
   }  

LeetCode: Binary Tree Level Order Traversal

Given a binary tree, return the level order traversal of its nodes' values. (ie, from left to right, level by level).

For example:
Given binary tree {3,9,20,#,#,15,7},

    3
   / \
  9  20
    /  \
   15   7

return its level order traversal as:

[
  [3],
  [9,20],
  [15,7]
]

confused what "{1,#,2,3}" means? > read more on how binary tree is serialized on OJ.

OJ's Binary Tree Serialization:

The serialization of a binary tree follows a level order traversal, where '#' signifies a path terminator where no node exists below.

Here's an example:

   1
  / \
 2   3
    /
   4
    \
     5

The above binary tree is serialized as "{1,2,3,#,#,4,#,#,5}".

 /**  
  * Definition for binary tree  
  * struct TreeNode {  
  *   int val;  
  *   TreeNode *left;  
  *   TreeNode *right;  
  *   TreeNode(int x) : val(x), left(NULL), right(NULL) {}  
  * };  
  */ 

 
   void inorder(TreeNode *root,int level, vector<vector<int> > &v)  
   {  
     if(!root)return;  
     inorder(root->left,level+1,v);  
     v[level].push_back(root->val);  
     inorder(root->right,level+1,v);  
   }  

   int depth(TreeNode *root)  
   {  
     if(!root)return 0;  
     return (max(depth(root->left),depth(root->right))+1);  
   }  

   vector<vector<int> > levelOrder(TreeNode *root) {  
     vector<vector<int> > v(depth(root));  
     inorder(root,0, v);  
     return v;  
   }  

LeetCode: Maximum Depth of Binary Tree

Given a binary tree, find its maximum depth.

The maximum depth is the number of nodes along the longest path from the root node down to the farthest leaf node.

 /**  
  * Definition for binary tree  
  * struct TreeNode {  
  *   int val;  
  *   TreeNode *left;  
  *   TreeNode *right;  
  *   TreeNode(int x) : val(x), left(NULL), right(NULL) {}  
  * };  
  */  

   int maxDepth(TreeNode *root) {  
     if(!root)return 0;  
     if(!root->left && !root->right)return 1;  
     int x = maxDepth(root->left);  
     int y = maxDepth(root->right);  
     return (max(x,y)+1);  
   }  

LeetCode: Convert Sorted List to Binary Search Tree

Given a singly linked list where elements are sorted in ascending order, convert it to a height balanced BST.

 /**  
  * Definition for singly-linked list.  
  * struct ListNode {  
  *   int val;  
  *   ListNode *next;  
  *   ListNode(int x) : val(x), next(NULL) {}  
  * };  
  */  

 /**  
  * Definition for binary tree  
  * struct TreeNode {  
  *   int val;  
  *   TreeNode *left;  
  *   TreeNode *right;  
  *   TreeNode(int x) : val(x), left(NULL), right(NULL) {}  
  * };  
  */  

   TreeNode *sortedListToBST(ListNode *head) {  
     if(!head)return NULL;  
     TreeNode *root = new TreeNode(head->val);  
     if(!head->next)return root;  
     ListNode *fast = head->next, *slow = head, *prev;  
     while(fast)  
     {  
       prev = slow;  
       slow = slow->next;  
       if(fast->next)  
         fast = fast->next->next;  
       else fast = fast->next;  
     }  
     root->val = slow->val;  
     prev->next = NULL;  
     root->left = sortedListToBST(head);  
     root->right = sortedListToBST(slow->next);  
     return root;  
   }  

LeetCode: Balanced Binary Tree

Given a binary tree, determine if it is height-balanced.

For this problem, a height-balanced binary tree is defined as a binary tree in which the depth of the two subtrees of every node never differ by more than 1.

 /**  
  * Definition for binary tree  
  * struct TreeNode {  
  *   int val;  
  *   TreeNode *left;  
  *   TreeNode *right;  
  *   TreeNode(int x) : val(x), left(NULL), right(NULL) {}  
  * };  
  */ 

 
   bool isBalancedRecurse(TreeNode *root, int *height)  
   {  
     if(!root)  
     {  
       *height = 0;  
       return true;  
     }  
     if(!root->left && !root->right)  
     {  
       *height = 1;  
       return true;  
     }  
     int lh = 0, rh = 0;  
     bool x = isBalancedRecurse(root->left,&lh);  
     bool y = isBalancedRecurse(root->right,&rh);  
     *height = max(lh,rh)+1;  
     return (abs(lh-rh)<=1 && x && y);  
   } 

 
   bool isBalanced(TreeNode *root) {  
     int height = 0;  
     return isBalancedRecurse(root,&height);  
   }  

LeetCode: Minimum Depth of Binary Tree

Given a binary tree, find its minimum depth.

The minimum depth is the number of nodes along the shortest path from the root node down to the nearest leaf node.

  /**  
  * Definition for binary tree  
  * struct TreeNode {  
  *   int val;  
  *   TreeNode *left;  
  *   TreeNode *right;  
  *   TreeNode(int x) : val(x), left(NULL), right(NULL) {}  
  * };  
  */  
   #define INT_MAX 0x7FFFFFFF


   int minDepth(TreeNode *root) {  
     if(root == NULL)return 0;  
     if(!root->left && !root->right)return 1;  
     int x = minDepth(root->left);  
     int y = minDepth(root->right);  
     if(!x)x = INT_MAX;  
     if(!y)y = INT_MAX;  
     return (min(x, y) +1);  
   }  

LeetCode: Path Sum

Given a binary tree and a sum, determine if the tree has a root-to-leaf path such that adding up all the values along the path equals the given sum.

For example:
Given the below binary tree and sum = 22,

              5
             / \
            4   8
           /   / \
          11  13  4
         /  \      \
        7    2      1

return true, as there exist a root-to-leaf path 5->4->11->2 which sum is 22.

 /**  
  * Definition for binary tree  
  * struct TreeNode {  
  *   int val;  
  *   TreeNode *left;  
  *   TreeNode *right;  
  *   TreeNode(int x) : val(x), left(NULL), right(NULL) {}  
  * };  
  */

    
   bool hasPathSum(TreeNode *root, int sum) {  
     if(!root)return false;  
     if(!root->left && !root->right && sum == root->val)  
     {  
       return true;  
     }  
     return (hasPathSum(root->left, sum-root->val) ||  
       hasPathSum(root->right, sum-root->val));  
   }  

LeetCode: Binary Tree Maximum Path Sum

Given a binary tree, find the maximum path sum.

The path may start and end at any node in the tree.

For example:
Given the below binary tree,

       1
      / \
     2   3

Return 6.

/**
 * Definition for binary tree
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
  #define INT_MIN 0x8FFFFFFF


  int MPSRecurse(TreeNode *root, int *sum)  
   {  
     if(root == NULL)return INT_MIN;  
     if(root->left == NULL && root->right == NULL)  
     {  
       *sum = root->val;  
       return root->val;  
     }  
     int lsum = INT_MIN, rsum = INT_MIN;  
     int x = MPSRecurse(root->left, &lsum);  
     int y = MPSRecurse(root->right, &rsum);  
     *sum = max(max(lsum,rsum)+root->val,root->val);  
     if(lsum<0)lsum = 0;  
     if(rsum<0)rsum = 0;  
     return (max(max(x,y), lsum + rsum + root->val));  
   }


  
   int maxPathSum(TreeNode *root) {  
     int sum = 0;  
     return MPSRecurse(root, &sum);  
   }  

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 1->2 represents the number 12.
The root-to-leaf path 1->3 represents the number 13.

Return the sum = 12 + 13 = 25.

/**
 * Definition for binary tree
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */


   void sumRootToLeaf(TreeNode *root, int num, int *res)  
   {  
     if(!root)return;  
     if(!root->left && !root->right )  
     {  
       *res += num *10 + root->val;  
       return;  
     }  
     sumRootToLeaf(root->left, 10*num+root->val,res);  
     sumRootToLeaf(root->right, 10*num+root->val,res);  
   }  
   int sumNumbers(TreeNode *root) {  
      int res = 0;  
      sumRootToLeaf(root,0,&res);  
      return res;  
   }