喜刷刷: balance

Wednesday, November 12, 2014

[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.

思路：
非常巧妙的题目，解答时参考了这篇文章： http://leetcode.com/2010/11/convert-sorted-list-to-balanced-binary.html

这题和Convert Sorted Array to Binary Search Tree那题看上去很像，但是从array变成了linked list，就不能O(1)寻找中间节点了。一种直接的修改就是每次遍历一半的节点来找寻中间节点。如何在不知道linked list总长的情况下遍历一半节点？双指针策略，快指针一次走2个节点，慢指针一次走1个节点，当快指针到尾部时，慢指针对应的即为中间节点。但这种方法的时间复杂度为O(N logN)：每层递归一共访问N/2个节点，一共log N层递归（对应树的高度）。

对于构建N节点的binary tree来说理论上算法复杂度最少只能到O(N)，因为生成N个节点本身就需要O(N)。要达到O(N)复杂度的算法，就不能反复遍历来查找中间节点，而只能顺序边访问linked list边构建树。这里的关键是利用构建left subtree的递归，来找寻middle节点。即构建left subtree的时候需要返回两个值：left subtree的root节点，以及整个left subtree在linked list中的下一个节点，即middle节点，也是整个left subtree的parent节点。

class Solution {
public:
    TreeNode *sortedListToBST(ListNode *head) {
        int listLen = 0;
        ListNode *cur = head;
        while(cur) {
            listLen++;
            cur = cur->next;
        }
        return sortedListToBST(head, 0, listLen-1);
    }
    
    TreeNode *sortedListToBST(ListNode *&head, int start, int end) {
        if(start>end) return NULL;
        int mid = start + (end-start)/2;
        TreeNode *leftChild = sortedListToBST(head, start, mid-1);
        TreeNode *root = new TreeNode(head->val);
        head = head->next;
        TreeNode *rightChild = sortedListToBST(head, mid+1, end);
        root->left = leftChild;
        root->right = rightChild;
        return root;
    }
};

总结：

这个方法非常不容易理解

TreeNode *sortedListToBST(ListNode *&head, int start, int end)

这个函数所做的是将*head为头的linked list构建成一个BST，然后返回BST的root，而同时，也将head移动到linked list中第end+1个节点。因为*head既是输入参数，也是返回参数，所以这里用到了指针的引用*&head。注意不能错写成了&*head。理解*&的方法是从右向左读：首先是一个引用，然后是一个对指针的引用，最后是一个对ListNode指针的引用。

那么当left subtree构建完成后，head指向了mid，构建mid树节点。然后后移head到right subtree在linked list中的头节点。继续递归构建right subtree.

跑一个例子：

linked list: 0->1->2->NULL

call (head(0), 0, 2)

mid = 1

node(1), head(2)

/ \

call (head(0), 0, 0) call (head(2), 2, 2)

mid = 0 mid = 2

node(0), head(1) node(2), head(NULL)

/ \ / \

call (head(0), 0, -1) call (head(0), 1, 0) call (head(2), 2, 1) call (head(0), 2, 1)

return NULL return NULL return NULL return NULL

最终结果：

/ \

0 2

Monday, November 10, 2014

[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.

思路：

1. Tree depth的定义：为当前节点左右subtree depth中的较大值加1.

depth(root) = max[ depth(root->left), depth(root->right) ] + 1

而对NULL节点的depth在有的书上定义为-1，有的书上定义为0。但这个定义并不影响对balance binary tree的判断，所以这里假设NULL节点的depth为0，即leaf节点的depth为1.

2. 如何判断balance？

(1). 一个binary tree中有任何一个subtree不平衡，那么整个tree不平衡。

(2) 当x->left和x->right的subtree都平衡时，只有abs(depth(x->left) - depth(x->right))<=1时，以x的subtree才平衡。

3. 如何递归？

Bottom-up递归，因为只有当某一节点左右子树的depth以及左右子树是否平衡都得知以后，才能判断该节点为根的树是否平衡，以及求得该节点的depth。

Base case: NULL节点depth返回0。

4. 函数返回什么？

函数即要返回当前节点为根的树的depth，以便于父节点判断平衡和计算depth。同时也需要返回该树是否平衡的判断。可以将两个返回值合并在一起：由于最小的depth为0（NULL节点），在返回depth时可以以 -1 来表示该子树不平衡。

class Solution {
public:
    bool isBalanced(TreeNode *root) {
        return findDepth(root)==-1 ? false : true;
    }
    
    int findDepth(TreeNode *root) {
        if(!root) return 0;
        
        int leftDepth = findDepth(root->left);      // left subtree depth
        if(leftDepth==-1) return -1;
        
        int rightDepth = findDepth(root->right);    // right subtree depth
        if(rightDepth==-1) return -1;
        
        if(abs(leftDepth-rightDepth)>1) return -1;
        
        return max(leftDepth,rightDepth)+1;
    }
};

总结：

代码中ln 11之所以不和ln 14合并放在ln 13之后，是因为当左子树不平衡时，没有必要再对右子树求depth，直接返回-1即可。这类代码中的剪枝优化需要经常注意。