ToB企服应用市场:ToB评测及商务社交产业平台

标题: 【C】链式二叉树算法题1 -- 单值二叉树 [打印本页]
作者: 科技颠覆者    时间: 10 小时前
标题: 【C】链式二叉树算法题1 -- 单值二叉树
leetcode链接
https://leetcode.cn/problems/univalued-binary-tree/description/
1  题目描述 

  如果二叉树每个节点都具有相同的值，那么该二叉树就是单值二叉树。只有给定的树是单值二叉树时，才返回 true；否则返回 false。
示例 1：



输入：[1,1,1,1,1,null,1]
输出：true
示例 2：



输入：[2,2,2,5,2]
输出：false
  通过示例与题目意思，我们应该理解了该题目的要求就是判断一棵二叉树全部节点的值是否都是相同的，如果都相同就返回 true，否则返回 false。
2  算法解析 

  对于一棵二叉树来说，其相关算法题一般都可以考虑用递归算法来解决，由于一棵二叉树就是递归定义的嘛。这道题的解法有这么几种情况：
1） 当根节点为空时，此为一棵单值二叉树。
2） 当根节点不为空且其左孩子也不为空，但是根节点的值跟左孩子节点的值不相同，说明其不是一棵单值二叉树。
3） 当根节点不为空且其右孩子也不为空，但是根节点的值不与右孩子的值相同时，说明其也不是一棵单值二叉树。
4） 整棵树是一棵单值二叉树又可递归定义为根节点的左子树是一棵单值二叉树且其右子树也是一棵单值二叉树。
  其中 4）为递归过程，前三条为界限条件。
3  代码

  1. typedef struct TreeNode TreeNode;
  2. bool isUnivalTree(struct TreeNode* root)
  3. {
  4.     //如果根结点为空，返回true
  5.     if (root == NULL)
  6.     {
  7.         return true;
  8.     }
  9.     //如果左孩子不为空，且根节点值不等于左孩子的值，返回false
  10.     if (root->left && root->val != root->left->val)
  11.     {
  12.         return false;
  13.     }
  14.     //如果右孩子不为空，且根节点值不等于右孩子的值，返回false
  15.     if (root->right && root->val != root->right->val)
  16.     {
  17.         return false;
  18.     }
  19.     //判断左子树与右子树是否都是一棵相同的树
  20.     return isUnivalTree(root->left) && isUnivalTree(root->right);
  21. }
复制代码
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。



欢迎光临 ToB企服应用市场:ToB评测及商务社交产业平台 (https://dis.qidao123.com/) Powered by Discuz! X3.4