C/C++教程

算法刷题:LC初级算法(五)

本文主要是介绍算法刷题:LC初级算法(五),对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

文章目录

    • 二叉树的最大深度
    • 验证二叉搜索树
    • 对称二叉树
    • 二叉树的层序遍历
    • 将有序数组转换为二叉搜索树

二叉树的最大深度

给定一个二叉树,找出其最大深度。

二叉树的深度为根节点到最远叶子节点的最长路径上的节点数。

说明: 叶子节点是指没有子节点的节点。

示例:
给定二叉树 [3,9,20,null,null,15,7],

    3
   / \
  9  20
    /  \
   15   7

返回它的最大深度 3 。

作者:力扣 (LeetCode)
链接:https://leetcode-cn.com/leetbook/read/top-interview-questions-easy/xnd69e/
来源:力扣(LeetCode) 著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。

思路:很直接,递归那一套。

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

验证二叉搜索树

给定一个二叉树,判断其是否是一个有效的二叉搜索树。

假设一个二叉搜索树具有如下特征:

节点的左子树只包含小于当前节点的数。
节点的右子树只包含大于当前节点的数。
所有左子树和右子树自身必须也是二叉搜索树。

示例 1:

输入:

    2
   / \
  1   3
输出: true

示例 2:

输入:

   5
   / \
  1   4
     / \
    3   6
输出: false

解释: 输入为: [5,1,4,null,null,3,6]。
根节点的值为 5 ,但是其右子节点值为 4 。

作者:力扣 (LeetCode)
链接:https://leetcode-cn.com/leetbook/read/top-interview-questions-easy/xn08xg/
来源:力扣(LeetCode) 著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。


思路:
对于这种二叉树,前序遍历取出来就是一个升序数列。

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

    
    bool isValidBST(TreeNode* root) {
        vector<int> temp;
        mrun(temp,root);
        for(int x = 0;x<temp.size()-1;x++){
            if(temp[x]>=temp[x+1])
                return false;
        }
        return true;
    }

对称二叉树

给定一个二叉树,检查它是否是镜像对称的。

例如,二叉树 [1,2,2,3,4,4,3] 是对称的。

	1
   / \
  2   2
 / \ / \
3  4 4  3

但是下面这个 [1,2,2,null,3,null,3] 则不是镜像对称的:

    1
   / \
  2   2
   \   \
   3    3

进阶:

你可以运用递归和迭代两种方法解决这个问题吗?

作者:力扣 (LeetCode)
链接:https://leetcode-cn.com/leetbook/read/top-interview-questions-easy/xn7ihv/
来源:力扣(LeetCode) 著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。


我用的是迭代的方式,将根的左右子树分别前序遍历和反前序遍历之后进行比对,但是这样会耗费一部分的存储空间。

void frrun(vector<int>& temp,TreeNode* root){
        if(root == NULL){
            temp.push_back(INT_MIN);
            return;
        }
            
        temp.push_back(root->val);
        frrun(temp,root->right);
        frrun(temp,root->left);
    }
    void flrun(vector<int>& temp,TreeNode* root){
        if(root == NULL)if(root == NULL){
            temp.push_back(INT_MIN);
            return;
        }
        temp.push_back(root->val);
        flrun(temp,root->left);
        flrun(temp,root->right);
    }
    bool isSymmetric(TreeNode* root) {
        vector<int> temp1;
        vector<int> temp2;

        frrun(temp1,root->right);
        flrun(temp2,root->left);

        if(temp1.size() != temp2.size())
            return false;
        
        for(int x = 0;x<temp1.size();x++)
            if(temp1[x] != temp2[x])
                return false;
        
        return true;
    }

二叉树的层序遍历

给你一个二叉树,请你返回其按 层序遍历 得到的节点值。 (即逐层地,从左到右访问所有节点)。

示例:
二叉树:[3,9,20,null,null,15,7],

    3
   / \
  9  20
    /  \
   15   7

返回其层序遍历结果:

[
  [3],
  [9,20],
  [15,7]
]

作者:力扣 (LeetCode)
链接:https://leetcode-cn.com/leetbook/read/top-interview-questions-easy/xnldjj/
来源:力扣(LeetCode) 著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。


vector<vector<int>> levelOrder(TreeNode* root) {
        vector<vector<int>> target;
        if(!root)
            return target;

        queue<TreeNode*> que;
        que.push(root);
        while(!que.empty()){
            // 当前队列中的元素都是同一层的,n为该层元素数目
            int n = que.size();
            // 定义一个容器存储该层的节点的val值
            vector<int> tv;
            while(n--){
                TreeNode* tn = que.front(); que.pop();
                tv.push_back(tn->val);
                if(tn->left)
                    que.push(tn->left);
                if(tn->right)
                    que.push(tn->right);
            }
            target.push_back(tv);
        }
        return target;
    }

将有序数组转换为二叉搜索树

给你一个整数数组 nums ,其中元素已经按 升序 排列,请你将其转换为一棵 高度平衡 二叉搜索树。

高度平衡 二叉树是一棵满足「每个节点的左右两个子树的高度差的绝对值不超过 1 」的二叉树。

这不就是我的面试题里面的一部分嘛、

TreeNode* check(vector<int>& nums, int Left, int Right) {
        if(Left > Right) {
            return nullptr;
        }
        int Mid = (Right + Left)/2;
        TreeNode * ret = new TreeNode(nums[Mid]);
        ret->left = check(nums, Left, Mid-1);
        ret->right = check(nums, Mid+1, Right);
        return ret;
    }

TreeNode* sortedArrayToBST(vector<int>& nums) {
    return check(nums, 0, nums.size()-1);
}
这篇关于算法刷题:LC初级算法(五)的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!