电子代加工东莞网站建设,qq官网首页登录,wordpress文章图片点击放大预览,wordpress小工具怎么使用今天我们一起来做一道初级的二叉树OJ题#xff0c;都是用递归思想解答
力扣965.单值二叉树 链接https://leetcode.cn/problems/univalued-binary-tree/description/ 所谓单值二叉树就是这棵二叉树的所有节点的值是相同的#xff0c;那我们要做这道题#xff0c;肯定要…今天我们一起来做一道初级的二叉树OJ题都是用递归思想解答
力扣965.单值二叉树 链接https://leetcode.cn/problems/univalued-binary-tree/description/ 所谓单值二叉树就是这棵二叉树的所有节点的值是相同的那我们要做这道题肯定要把这棵树的所有结点遍历一遍看看所有结点的值是否相等。那怎么遍历呢二叉树有前序遍历、中序遍历、后序遍历和层次遍历对于这道题而言要看所有结点的值是否相等无疑前序遍历是最方便的因为我们只有先检查了根节点的值是一直才能继续遍历左右子树。所以我们开始解答这道题
我们想如果这棵树是一棵空树该怎么处理 我们认为如果是一棵空树就返回true
即
if(rootNULL){return true;}
接下来走到这里肯定就不为空树但是左右子树还是有可能一边是空的那我们分开处理。如果左子树不为空在这个前提下要是左子树的值等于根节点的值我们返回true但是我们这样写还是到后面会麻烦因为只要左子树的值等于根节点的值就true的话那左子树的左子树呢后面就不会判断到所以我们这里还是以不相等的条件进行处理即
if(root-left!NULLroot-left-val!root-val){return false;}
同理右子树不为空我们可以写成
if(root-right!NULLroot-right-val!root-val){return false;}
空树、左右子树都不为空的情况我们都判断了那走到这里就是根节点的左右子树都等于根节点的值那我们就继续以根节点的左子树为根根节点的右子树为根判断了并且这两个必须同时满足那才能返回true即
return isUnivalTree(root-left)isUnivalTree(root-right);
我们运行提交就通过啦 完整代码
bool isUnivalTree(struct TreeNode* root) {if(rootNULL)//为空的情况{return true;}if(root-left!NULLroot-left-val!root-val)//左子树不为空且左子树不等于根{return false;}if(root-right!NULLroot-right-val!root-val)//右子树不为空且右子树不等于根{return false;}return isUnivalTree(root-left)isUnivalTree(root-right);//左右子树等于根的值继续下面的左右子树}
