11.分治算法

分治算法是將一個(gè)大問題分成幾個(gè)小問題來進(jìn)行處理

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.

一顆二叉樹是平衡的，當(dāng)且僅當(dāng)左右兩個(gè)子樹的高度差的絕對(duì)值不超過1吐葵，并且左右兩個(gè)子樹都是一棵平衡二叉樹景醇。

當(dāng)node為空的時(shí)候畏吓，高度為0，當(dāng)node不為空的時(shí)候迅脐，高度為左、右子樹中高度較高的那個(gè)的高度再加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);
}

//缺點(diǎn)：重復(fù)計(jì)算較多

示例2（改進(jìn)版）：


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不斷地減去各個(gè)路徑上節(jié)點(diǎn)的value丁鹉，然后用于下次遞歸妒潭，直到某個(gè)節(jié)點(diǎn)值正好等于遞減后的sum悴能，我們便存儲(chǔ)該路徑。

示例代碼：


//path：存儲(chǔ)我們走過的具體路徑
//result：存儲(chǔ)符合條件的路徑雳灾，可含多個(gè)
//root：根節(jié)點(diǎn)
//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

給你一個(gè)前序漠酿、中序字符串構(gòu)建一個(gè)二叉樹數(shù)據(jù)結(jié)構(gòu)