Sunday, August 2, 2015

GeeksforGeeks: Diameter of a Binary Tree, Inorder Successor in Binary Search Tree

Diameter of a Binary Tree
http://www.geeksforgeeks.org/diameter-of-a-binary-tree/

在返回想要的值的同时,传入pointer计算树的高度
int helper(TreeNode *root, int *height) {
    if (root == NULL) {
        *height = 0;
        return 0;
    }
    int lh = 0, rh = 0;
    int leftD = helper(root->left,&lh);
    int rightD = helper(root->right,&rh);
    
    *height = max(lh,rh) + 1;
    return max(lh + rh + 1,max(leftD,rightD));
}

int getDiameter(TreeNode *root) {
    int longest = 0;
    helper(root,longest);
    
    return longest;
}
--------------------------------------
Inorder Successor in Binary Search Tree
写法1:http://www.geeksforgeeks.org/inorder-successor-in-binary-search-tree/
写法2:
同样的写法可以用来计算floor function
TreeNode *myFloor(TreeNode *root,int key) {
    if (root == NULL) return NULL;
    
    if (key >= root->val) {
        return myFloor(root->right,key);    
    }else {
        TreeNode *right = myFloor(root->left,key);
        if (right == NULL) return root;
        else return right;
    }
}

No comments:

Post a Comment