剑指offer每日一练

一. 剑指 Offer 55 - I. 二叉树的深度

题目：

输入一棵二叉树的根节点，求该树的深度。从根节点到叶节点依次经过的节点（含根、叶节点）形成树的一条路径，最长路径的长度为树的深度。

解题思路：?

利用队列对树进行遍历，每遍历一层，对计数器进行+1，遍历完整个树即可得到树的深度。

C++代码：

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    int maxDepth(TreeNode* root) {
        if(root == nullptr) return 0;

        queue<TreeNode*> A;
        A.push(root);
        int sum = 0;
        while(!A.empty())
        {
            int cnt = A.size();
            for(int i = 0; i < cnt; i++ )
            {
                TreeNode* node = A.front();
                A.pop();
                if(node -> left) A.push(node -> left);
                if(node -> right) A.push(node -> right);
            }
            sum++;
        }
        return sum;
    }
};

二. 剑指 Offer 55 - II. 平衡二叉树

题目：

输入一棵二叉树的根节点，判断该树是不是平衡二叉树。如果某二叉树中任意节点的左右子树的深度相差不超过1，那么它就是一棵平衡二叉树。

解题思路：?

思路是构造一个可以求树的深度的函数 depth(root)（如上面一题），通过比较某子树的左右子树的深度差 abs(depth(root? ->? left)? -? depth(root? ->? right))? <=? 1 是否成立，来判断某子树是否是二叉平衡树。若所有子树都平衡，则此树平衡。

C++代码：

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    bool isBalanced(TreeNode* root) {
        if(root == nullptr) return true;
        int m = depth(root -> left);
        int n = depth(root -> right);
        if(abs(m- n) <= 1 && isBalanced(root -> left) && isBalanced(root -> right))
            return true;
        else
            return false;
    }

private:
    int depth(TreeNode* root){
        if(root == nullptr) return 0;

        queue<TreeNode*> A;
        A.push(root);

        int sum = 0;
        while(!A.empty())
        {
            int cnt = A.size();
            for(int i = 0; i < cnt; i++ )
            {
                TreeNode* node = A.front();
                A.pop();
                if(node -> left) A.push(node -> left);
                if(node -> right) A.push(node -> right);
            }
            sum++;
        }
        
        return sum;
    }
};

三. 剑指 Offer 64. 求 1 + 2 + … + n

题目：

求?1 + 2?+ ... + n?，要求不能使用乘除法、for、while、if、else、switch、case等关键字及条件判断语句（A?B:C）。

示例：

输入：n = 3

输出：6

解题思路：?

递归

由A && B得，

当A为真时才判断B是否为真，

当A为假时跳过B的。

所以将递归式子放在B中，A中放入递归的中止条件

C++代码：

class Solution {
public:
    int sumNums(int n) {
        (n > 1) && (n += sumNums(n-1));
        return n;
    }
};

四. 剑指 Offer 68 - I. 二叉搜索树的最近公共祖先

题目：

给定一个二叉搜索树, 找到该树中两个指定节点的最近公共祖先。

最近公共祖先的定义为：“对于有根树 T 的两个结点 p、q，最近公共祖先表示为一个结点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。”

示例：

输入：root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 8

输出：6

解题思路：?

若root 是 p 和 q 的最近公共祖先，则只有一下三中情况：

• p = root 且 q 在 root 的左子树或右子树中
• q = root 且 p?在 root 的左子树或右子树中
• p 和 q分别在 root 的左右子树中；?

因为该树为搜索二叉树，所以右节点均大于左节点可得：

• 如果 root -> val? <? p -> val，表示 p 在 root 的右子树中；
• 如果 root -> val? >? p -> val，表示 p 在 root 的左子树中；
• 如果 root -> val? =? p -> val，表示 p 和?root 的指向同一节点

结合上述进行递归查找：

当 p 和 q 同时在 root 的左子树（或右子树）中， 则开启左子树（或右子树）的递归。

C++代码：

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        if(root -> val < p -> val && root -> val < q -> val)
            return lowestCommonAncestor(root -> right, p, q);
        if(root -> val > p -> val && root -> val > q -> val)
            return lowestCommonAncestor(root -> left, p, q);
        return root;
    }
};

五.?剑指 Offer 68 - II. 二叉树的最近公共祖先

题目：

给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。

最近公共祖先的定义为：“对于有根树 T 的两个结点 p、q，最近公共祖先表示为一个结点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。”

示例：

输入：root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 1

输出：3

解题思路：?

递归（回头补）

C++代码：

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        if(root == nullptr || root == p || root == q) return root;
        TreeNode* left = lowestCommonAncestor(root -> left, p, q);
        TreeNode* right = lowestCommonAncestor(root -> right, p, q);
        if(left == nullptr && right == nullptr) return nullptr;
        if(left == nullptr) return right;
        if(right == nullptr) return left;
        return root;
    }
};