剑指Offer

[FanDoubleLucky]

数值的整数次方

题目描述 给定一个double类型的浮点数base和int类型的整数exponent。求base的exponent次方。 此题的考点是要考虑多种情况，exponent是正还是负还是零，要分情况处理，此外，通过平方来快速减小正整数次方运算，a^15=a*(a^2)^7

class Solution {
public:
    double Power(double base, int exponent) {
        int n = exponent;
        if(exponent<0){
            n = -1*exponent;
        }
        else if(exponent==0){
            return 1;
        }
        double cur = base, res = 1;
        while(n>0){
            if((n&1)==1){
                res*=cur;
            }
            cur*=cur;
            n>>=1;
        }
        return exponent>0?res:(1/res);
    }
};

[FanDoubleLucky]

树的子结构

题目描述 输入两棵二叉树A，B，判断B是不是A的子结构。（ps：我们约定空树不是任意一个树的子结构） 基本思路是递归，对每个节点进行一次是否是相等的树结构的操作，而每一次是否是相等的树结构的操作也是通过递归实现，先判断根节点是否相等，再判断左右节点是否相等，直至为空。

/*
struct TreeNode {
    int val;
    struct TreeNode *left;
    struct TreeNode *right;
    TreeNode(int x) :
            val(x), left(NULL), right(NULL) {
    }
};*/
class Solution {
public:
    bool HasSubtree(TreeNode* pRoot1, TreeNode* pRoot2)
    {
        bool res = false;
        if(pRoot1!=NULL&&pRoot2){
            if(pRoot1->val==pRoot2->val){
                res = equal(pRoot1, pRoot2);
            }
            if(!res){//pRoot1根节点处没有pRoot2这样的子结构，所以再判断pRoot1的左节点
                res = HasSubtree(pRoot1->left, pRoot2);
            }
            if(!res){//pRoot1左节点处没有pRoot2这样的子结构，所以再判断pRoot1的右节点
                res = HasSubtree(pRoot1->right, pRoot2);
            }
        }
        return res;
    }

    bool equal(TreeNode* node1, TreeNode* node2){
        if(node1==NULL&&node2!=NULL){//node1已经遍历空，node2还没有，所以没有node2这样的子结构
            return false;
        }
        else if(node2==NULL){//node2已经遍历结束，node1此时可以为空也可以不为空，因为找的是子结构，不需要完全一样
            return true;
        }
        else if(node1->val!=node2->val){
            return false;
        }
        else return equal(node1->left, node2->left)&equal(node1->right, node2->right);
    }
};

[FanDoubleLucky]

二叉树的镜像

题目描述 操作给定的二叉树，将其变换为源二叉树的镜像。 先交换目前节点的左右节点，再将已经完成交换的左右节点分别当做根节点交换它们的左右节点。

/*
struct TreeNode {
    int val;
    struct TreeNode *left;
    struct TreeNode *right;
    TreeNode(int x) :
            val(x), left(NULL), right(NULL) {
    }
};*/
class Solution {
public:
    void Mirror(TreeNode *pRoot) {
        if(pRoot==NULL){
            return;
        }
        TreeNode* temp = pRoot->right;
        pRoot->right = pRoot->left;
        pRoot->left = temp;
        Mirror(pRoot->left);
        Mirror(pRoot->right);
    }
};