单值二叉树

2023-12-31 16:36:18

说在前面

🎈不知道大家对于算法的学习是一个怎样的心态呢?为了面试还是因为兴趣?不管是出于什么原因,算法学习需要持续保持。

题目描述

只有给定的树是单值二叉树时,才返回 true;否则返回 false。
示例 1:

输入:[1,1,1,1,1,null,1]
输出:true

示例 2:

输入:[2,2,2,5,2]
输出:false

提示:

给定树的节点数范围是 [1, 100]。
每个节点的值都是整数,范围为 [0, 99] 。

思路分析

今天的这道题目就是一道简单的考察二叉树的遍历的题目,我们可以从前序遍历、中序遍历、后序遍历、层级遍历中随意选择自己喜欢的方式来进行解题。

  • 前序遍历
    遍历顺序为:根节点->左子树->右子树
  • 中序遍历
    遍历顺序为:左子树->根节点->右子树
  • 后序遍历
    遍历顺序为:左子树->右子树->根节点
  • 层级遍历
    遍历顺序为:深度为0的节点->深度为1的节点->……->深度为n的节点

AC代码

  • 代码一
    使用dfs进行前序遍历,判断父子节点是否相等即可。
/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @return {boolean}
 */
var isUnivalTree = function(root) {
    let res = true;
    let dfs = function(r,val = null){
        if(!r || !res) return;
        if(val != null && r.val != val){
            res = false;
            return;
        }
        dfs(r.left,r.val);
        dfs(r.right,r.val);
    }
    dfs(root);
    return res;
};
  • 代码二
    使用递归的方式不停往下判断父子节点是否相等
/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @return {boolean}
 */
var isUnivalTree = function(root,val = null) {
    const left = (root.left == null ||
                (root.val == root.left.val && isUnivalTree(root.left)));
    const right = (root.right == null ||
            (root.val == root.right.val && isUnivalTree(root.right)));
    return left && right;
};

公众号

关注公众号『前端也能这么有趣』,获取更多有趣内容。

说在后面

🎉 这里是 JYeontu,现在是一名前端工程师,有空会刷刷算法题,平时喜欢打羽毛球 🏸 ,平时也喜欢写些东西,既为自己记录 📋,也希望可以对大家有那么一丢丢的帮助,写的不好望多多谅解 🙇,写错的地方望指出,定会认真改进 😊,偶尔也会在自己的公众号『前端也能这么有趣』发一些比较有趣的文章,有兴趣的也可以关注下。在此谢谢大家的支持,我们下文再见 🙌。

文章来源:https://blog.csdn.net/Twinkle_sone/article/details/135316887
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。