11.分治算法

---

分治算法是将一个大问题分成几个小问题来进行处理

Divide & Conquer Algorithm

• Merge Sort
• Quick Sort
• Most of the Binary Tree Problems!

Tree Depth

Compute the depth of a binary tree.比较左右两边的深度

int treeDepth(TreeNode *node) {
    if (node == NULL)
        return 0;
    else
        return max(treeDepth(node->left),treeDepth(node->right)) + 1;
}

Subtree

Tree1 and Tree2 are both binary trees nodes having value, determine if Tree2 is a subtree of Tree1.
判断root2是不是root1的子树

bool subTree(TreeNode *root1, TreeNode *root2){
    if (root2 == NULL) {
        return true;
    }
    if (root1 == NULL) { //we have exhauste the root1 already
        return false;
    }
    if (root1->val == root2->val) {
        if (matchTree(root1, root2)) {
            return true;
        }
    }
    return isSubTree(root1->left, root2) || isSubTree(root1->right, root2);
}

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

Balanced Binary Tree

Determine if a binary tree is a balanced tree.

一颗二叉树是平衡的，当且仅当左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树。

当node为空的时候，高度为0，当node不为空的时候，高度为左、右子树中高度较高的那个的高度再加1

示例1：

int level(TreeNode *root){
    if(root ==  NULL)
        return 0;
    return max(level(root->left), level(root->right)) + 1;
}
bool isBalanced(TreeNode* root){
    if(root ==  NULL)
        return true;
    int factor = abs(level(root->left) - level(root->right));
    return factor < 2 && isBalanced(root->right) && isBalanced(root->left);
}

//缺点：重复计算较多

示例2（改进版）：

int isBalancedHelper(TreeNode *root) {
    if (root == NULL) {
       return 0;
    }
    int leftHeight = isBalance(root->left);
    if (leftHeight == INBALANCE) {
        return INBALANCE;
    }
    int rightHeight = isBalance(root->right);
    if (rightHeight == INBALANCE) {
        return INBALANCE;
    }

    if (abs(leftHeight - rightHeight) > 1) {
        return INBALANCE;
    }

    return max(leftHeight, rightHeight) + 1;    // return height
}

bool isBalancedTree(TreeNode *root) {
    return (isBalancedHelper(root) != INBALANCE)
}

Path Sum

Get all the paths (always starts from the root) in a binary tree, whose sum would be equal to given value.
从root开始，寻找路径value之和为给定sum的路径。

解题思路：使用递归，从root开始让sum不断地减去各个路径上节点的value，然后用于下次递归，直到某个节点值正好等于递减后的sum，我们便存储该路径。

示例代码：

//path：存储我们走过的具体路径
//result：存储符合条件的路径，可含多个
//root：根节点
//sum：给定的求和值

void pathSumHelper(vector<int> path, vector<vector<int>> &result, TreeNode *root, int sum){
    if(root == NULL)
        return;
    path.push_back(root->val);
    if(root->val == sum){
        result.push_back(path);
    }
    pathSumHelper(path, result, root->left, sum - root->val);
    pathSumHelper(path, result, root->right, sum - root->val);
}

vector<vector<int> > pathSum(TreeNode *root, int sum) {
    vector<int> path;
    vector<vector<int>> result;
    pathSumHelper(path, result, root, sum);
    return result;
}

Rebuild Binary Tree

给你一个前序、中序字符串构建一个二叉树数据结构

示例代码：

//pstr:前序
//istr:中序
//n:所给字符串的长度

// preorder and inorder rebuild
TreeNode* rebuild(char *pstr, char *istr, int n) {
    if (n <= 0)
        return NULL;

    TreeNode* root = new TreeNode;
    root->data = *pstr;

    char* iter;
    for (iter = istr; iter < istr + n; iter++) {

        //当中序遍历到前序首节点时（根节点）意味着找到了分割点
        if (*iter == *pstr)
            break;
    }

    int k = iter - istr;
    root->left = rebuild(pstr + 1, istr, k);
    root->right = rebuild(pstr + k + 1, iter + 1, n - k - 1);

    return root;
}

---