LIKE CODING: Tree

Showing posts with label Tree. Show all posts

Saturday, February 13, 2016

LeetCode [333] Largest BST Subtree

Ref

[1] https://leetcode.com/problems/largest-bst-subtree/

Saturday, October 31, 2015

LeetCode [298] Binary Tree Longest Consecutive Sequence

298. Binary Tree Longest Consecutive Sequence

Medium

Given a binary tree, find the length of the longest consecutive sequence path.

The path refers to any sequence of nodes from some starting node to any node in the tree along the parent-child connections. The longest consecutive path need to be from parent to child (cannot be the reverse).

Example 1:

Input:

   1
    \
     3
    / \
   2   4
        \
         5

Output: 3

Explanation: Longest consecutive sequence path is 3-4-5, so return 3.

Example 2:

Input:

   2
    \
     3
    / 
   2    
  / 
 1

Output: 2 

Explanation: Longest consecutive sequence path is 2-3, not 3-2-1, so return 2.

//C++: 40ms dfs recursive
/**
 * 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:
    int longestConsecutive(TreeNode* root) {
        if(!root) return 0;
        int ret = 1;
        lc(root, ret, root->val, 1);
        return ret;
    }
    void lc(TreeNode* root, int &ret, int parent, int len){
        if(!root) return;
        if(root->val == parent+1){
            ret = max(ret, len+1);
        }else{
            len = 0;            
        }
        lc(root->left, ret, root->val, len+1);
        lc(root->right, ret, root->val, len+1);        
    }
};

//C++: 48ms dfs iterative
/**
 * 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:
    int longestConsecutive(TreeNode* root) {
        if(!root) return 0;
        stack<pair<TreeNode*, int>> stk;
        stk.push(pair<TreeNode*, int>(root, 1));
        int ret = 1;
        while(!stk.empty()){
            TreeNode* t = stk.top().first;
            int cur = stk.top().second;
            stk.pop();
            if(t->left){
                if(t->left->val == t->val+1){
                    stk.push(pair<TreeNode*, int>(t->left, cur+1));
                    ret = max(ret, cur+1);
                }else{
                    stk.push(pair<TreeNode*, int>(t->left, 1));
                }
            }
            if(t->right){
                if(t->right->val == t->val+1){
                    stk.push(pair<TreeNode*, int>(t->right, cur+1));
                    ret = max(ret, cur+1);
                }else{
                    stk.push(pair<TreeNode*, int>(t->right, 1));
                }
            }            
        }
        return ret;
    }
};

//C++: 44ms bfs iterative
/**
 * 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:
    int longestConsecutive(TreeNode* root) {
        if(!root) return 0;
        queue<pair<TreeNode *, int>> que;
        que.push(pair<TreeNode *, int>(root, 1));
        int ret = 1;
        while(!que.empty()){
            TreeNode * t = que.front().first;
            int cur = que.front().second;
            que.pop();
            if(t->left){
                if(t->left->val == t->val+1){
                    ret = max(ret, cur+1);
                    que.push(pair<TreeNode *, int>(t->left, cur+1));
                }else{
                    que.push(pair<TreeNode *, int>(t->left, 1));
                }
            }
            if(t->right){
                if(t->right->val == t->val+1){
                    ret = max(ret, cur+1);
                    que.push(pair<TreeNode *, int>(t->right, cur+1));
                }else{
                    que.push(pair<TreeNode *, int>(t->right, 1));
                }
            }
        }
        return ret;
    }
};

Monday, October 26, 2015

LeetCode [297] Serialize and Deserialize Binary Tree

297. Serialize and Deserialize Binary Tree

Hard

Serialization is the process of converting a data structure or object into a sequence of bits so that it can be stored in a file or memory buffer, or transmitted across a network connection link to be reconstructed later in the same or another computer environment.

Design an algorithm to serialize and deserialize a binary tree. There is no restriction on how your serialization/deserialization algorithm should work. You just need to ensure that a binary tree can be serialized to a string and this string can be deserialized to the original tree structure.

Clarification: The input/output format is the same as how LeetCode serializes a binary tree. You do not necessarily need to follow this format, so please be creative and come up with different approaches yourself.

Example 1:

Input: root = [1,2,3,null,null,4,5]
Output: [1,2,3,null,null,4,5]

Example 2:

Input: root = []
Output: []

Example 3:

Input: root = [1]
Output: [1]

Example 4:

Input: root = [1,2]
Output: [1,2]

Constraints:

The number of nodes in the tree is in the range [0, 104].
-1000 <= Node.val <= 1000

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Codec {
    void serialize(TreeNode* node, stringstream &ss){
        if(!node)
        {
            ss<<"# ";
        }
        else
        {
            ss<<node->val<<" ";
            serialize(node->left, ss);
            serialize(node->right, ss);
        }
    }
    
    TreeNode* deserialize(stringstream &ss)
    {
        string s;
        ss>>s;
        if(s=="#"){
            return NULL;
        }else{
            TreeNode* node = new TreeNode(stoi(s));
            node->left = deserialize(ss);
            node->right = deserialize(ss);
            return node;
        }
    }
public:

    // Encodes a tree to a single string.
    string serialize(TreeNode* root) {
        stringstream ss;
        serialize(root, ss);
        return ss.str();
    }

    // Decodes your encoded data to tree.
    TreeNode* deserialize(string data) {
        stringstream ss;
        ss<<data;
        return deserialize(ss);
    }
};

// Your Codec object will be instantiated and called as such:
// Codec codec;
// codec.deserialize(codec.serialize(root));

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Codec {
    String str;
    String[] strs;
    int index = 0;
    // Encodes a tree to a single string.
    public String serialize(TreeNode root) {
        str = "";
        sh(root);
        return str;
    }
    
    void sh(TreeNode node){
        if(str.length()>0) str += ",";
        if(node==null){
            str += "#";
        }else{
            str += node.val;
            sh(node.left);
            sh(node.right);
        }
    }

    // Decodes your encoded data to tree.
    public TreeNode deserialize(String data) {
        strs = data.split(",");
        index = 0;
        return dh();
    }
    
    TreeNode dh(){
        TreeNode node;
        String s = strs[index++];
        if(s.equals("#")){
            node = null;
        }else{
            node = new TreeNode(Integer.parseInt(s));
            node.left = dh();
            node.right = dh();
        }
        return node;
    }
}

// Your Codec object will be instantiated and called as such:
// Codec ser = new Codec();
// Codec deser = new Codec();
// TreeNode ans = deser.deserialize(ser.serialize(root));

Monday, September 21, 2015

LeetCode [285] Inorder Successor in BST

Ref
[1] https://leetcode.com/problems/inorder-successor-in-bst/
OJ

Monday, August 31, 2015

MJ [35] Print Tree Vertically

Ref
[1] http://www.geeksforgeeks.org/print-binary-tree-vertical-order/
Question
[2] http://www.mitbbs.com/article_t1/JobHunting/32925369_0_1.html

Sunday, August 30, 2015

LeetCode [272] Closest Binary Search Tree Value II

Ref
[1] https://leetcode.com/problems/closest-binary-search-tree-value-ii/
[2] https://leetcode.com/discuss/55240/ac-clean-java-solution-using-two-stacks

Wednesday, August 26, 2015

LeetCode [270] Closest Binary Search Tree Value

270. Closest Binary Search Tree Value

Easy

Given the root of a binary search tree and a target value, return the value in the BST that is closest to the target.

Example 1:

Input: root = [4,2,5,1,3], target = 3.714286
Output: 4

Example 2:

Input: root = [1], target = 4.428571
Output: 1

Constraints:

The number of nodes in the tree is in the range [1, 104].
0 <= Node.val <= 109
-109 <= target <= 109

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    int value = -1;
    public int closestValue(TreeNode root, double target) {
        helper(root, target);
        return value;
    }
    
    void helper(TreeNode node, double target){
        if(node==null) return;
        if(value == -1 || Math.abs(value-target)>Math.abs(node.val-target)){
            value = node.val;
        }
        if(target<node.val) helper(node.left, target);
        if(target>node.val) helper(node.right, target);
    }
}

Sunday, August 16, 2015

MJ [12] Print BST keys in the given range

Ref
[1] http://www.mitbbs.com/article_t/JobHunting/33010083.html
MJ
[2] http://www.geeksforgeeks.org/print-bst-keys-in-the-given-range/
Question

Saturday, August 15, 2015

LeetCode [257] Binary Tree Paths

Ref
[1] https://leetcode.com/problems/binary-tree-paths/
OJ

Wednesday, August 12, 2015

LeetCode [255] Verify Preorder Sequence in Binary Search Tree

Ref
[1] https://leetcode.com/problems/verify-preorder-sequence-in-binary-search-tree/
OJ

MJ [6] Diameter of a Binary Tree

Ref
[1] http://www.geeksforgeeks.org/diameter-of-a-binary-tree/
Question
[2] http://www.mitbbs.com/article_t/JobHunting/33025655.html

Wednesday, August 5, 2015

LeetCode [250] Count Univalue Subtrees

250. Count Univalue Subtrees

Medium

Given the root of a binary tree, return the number of uni-value subtrees.

A uni-value subtree means all nodes of the subtree have the same value.

Example 1:

Input: root = [5,1,5,5,5,null,5]
Output: 4

Example 2:

Input: root = []
Output: 0

Example 3:

Input: root = [5,5,5,5,5,null,5]
Output: 6

Constraints:

The numbrt of the node in the tree will be in the range [0, 1000].
-1000 <= Node.val <= 1000

//C++: 4ms
/**
 * 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:
    int countUnivalSubtrees(TreeNode* root) {
        int cnt = 0;
        helper(root, cnt);
        return cnt;
    }
    bool helper(TreeNode* root, int &cnt){
        if(!root) return true;
        bool left = helper(root->left, cnt);
        bool right = helper(root->right, cnt);
        if(!left || !right) return false;
        if(root->left && root->left->val!=root->val) return false;
        if(root->right && root->right->val!=root->val) return false;
        cnt++;
        return true;
    }
};

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    int ret = 0;
    public int countUnivalSubtrees(TreeNode root) {
        isUni(root);
        return ret;
    }
    
    boolean isUni(TreeNode root){
        if (root==null) return true;
        boolean left = isUni(root.left);
        boolean right = isUni(root.right);
        
        int v = root.val;
        if(!left || !right) return false;
        if(root.left!=null && root.left.val!=v) return false;
        if(root.right!=null && root.right.val!=v) return false;
        ret ++;
        return true;
    }
}