C语言单值二叉树
CodeWinter 人气:0【OJ - 二叉树】单值二叉树
LeetCode链接:单值二叉树
题目难度:简单
一、题目描述
如果二叉树每个节点都具有相同的值,那么该二叉树就是 单值 二叉树。
只有给定的树是单值二叉树时,才返回 true;否则返回 false。
二、解题思路
二叉树的递归遍历,一般都会把问题拆分成 当前树(根节点) 和 子树,然后子树又进行拆分,来解决问题。
核心思路:
1.先判断当前节点是否为空,如果为空,返回 true(空树也满足单值二叉树的条件)
2.判断当前树是不是单值二叉树:
- 先判断当前节点的左孩子是否为空;
- 将 当前节点的值 与 左孩子的值 进行比较,如果相等,在右孩子不为空的情况下,继续与 右孩子的值 进行比较;
- 如果不相等,说明 当前树 不是单值二叉树,返回 false。
3.继续往下递归遍历,判断当前节点的左右子树是不是单值二叉树。
递归过程演示:
如果 a == b && a == c 为真,说明 1 是单值二叉树。
分而治之,不断迭代,先判断 1 是不是单值二叉树,再判断 2 是不是单值二叉树,最后判断 3 是不是单值二叉树。
/** * Definition for a binary tree node. * struct TreeNode { * int val; * struct TreeNode *left; * struct TreeNode *right; * }; */ bool isUnivalTree(struct TreeNode* root){ // 1. 先判断当前节点是否为空 if(root == NULL) { return true; // 空树满足单值二叉树的条件 } // 2. 判断当前节点和其左右孩子是否是单值二叉树 // 先判断当前节点的左孩子是否为空,并将当前节点的值与左孩子的值进行比较,看是否相等, // 如果相等,则继续往下遍历;如果不相等,说明不是单值二叉树,则返回false。 if(root->left && root->val != root->left->val) { return false; } if(root->right && root->val != root->right->val) { return false; } // 3. 往下遍历,判断当前节点的左右子树是不是单值二叉树 return isUnivalTree(root->left) && isUnivalTree(root->right); }
代码中有个小思路,我们 if 的条件写的是,如果左孩子不为空,且当前节点的值 != 左孩子的值,则返回 false,那为什么不写成:如果左孩子不为空,且当前节点的值 == 左孩子的值,则怎么怎么样……呢?因为写 ==,不能直接得出一个结果,而写 !=,就能得出结果 flase。
加载全部内容