LeetCode 965. Univalued Binary Tree

简介: LeetCode 965. Univalued Binary Tree

A binary tree is univalued if every node in the tree has the same value.

Return true if and only if the given tree is univalued.

Example 1:


1100338-20190104092353405-1007685324.png



Input: [1,1,1,1,1,null,1]
Output: true

Example 2:


1100338-20190104092352591-1226199608.png



Input: [2,2,2,5,2]
Output: false

Note:

  1. The number of nodes in the given tree will be in the range [1, 100].
  2. Each node's value will be an integer in the range [0, 99].

题目描述:大概意思就是问我们给定一棵树,判断这棵树上的所有节点的值是不是相同的,相同即为 true ,不相同为 false

题目分析:判断一棵树的所有节点的值是不是相同的,可以分为以下几个条件:

  • 节点是否为空
  • 左子节点和父节点是否相同
  • 右子节点和父节点是否相同
  • 左子节点和右子节点是否相同

根据这个思路我们可以解决这个问题。

python 代码:

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
class Solution(object):
    def isUnivalTree(self, root):
        """
        :type root: TreeNode
        :rtype: bool
        """
        left_correct = not root.left or root.val == root.left.val and self.isUnivalTree(root.left)
        right_correct = not root.right or root.val == root.right.val and self.isUnivalTree(root.right)
        return left_correct and right_correct

C++ 代码:

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    int temp;
    bool flag = true;
    bool isUnivalTree(TreeNode* root) {
        if(!root){
            return true;
        }
        temp = root->val;
        travelTree(root);
        return flag;    
    }
    void travelTree(TreeNode* root){
        if(root){
            travelTree(root->left);
            travelTree(root->right);
            if(flag){
                flag = root->val == temp ? true : false;
            }
        }
    }
};



目录
相关文章
|
Java
Leetcode 114. Flatten Binary Tree to Linked List
思路也很简单,先把root的左子树(如有)变成单链表 leftlinkedlist,把root的右子树(如有)变成单链表 rightlinkedlist,再把root的右节点变成leftlikedlist,再把rightlinkedlist接到leftlinkedlist后面,代码如下。
45 1
Leetcode Minimum Depth of Binary Tree (面试题推荐)
计算树的最小深度 很简单的一道题,只需要遍历一次树,到叶子节点的时候计算一下深度和当前最小深度比较,保存最小值就行。 我在这用了一个全局变量 mindepth。总感觉我这代码写的不够简练,求更精简的方法。
47 0
Leetcode Binary Tree Postorder Traversal(面试题推荐)
非递后续归遍历二叉树,肯定得用到栈。先序遍历很好写,但后续遍历就不是那么容易了。 只需要设置个指针pre,指向最后输出的那个节点就行了,只要判断cur指针指向的是上次输出节点的父节点,且cur无其他未遍历的节点,这个时候就把cur节点输出即可,然后更改pre。原理是要遍历当前节点,其所有子节点都必须遍历完,因为肯定是先左后右,所以只需一个指针保持前一次输出的结果即可。
51 0
Leetcode 236. Lowest Common Ancestor of a Binary Tree
根据LCA的定义,二叉树中最小公共祖先就是两个节点p和q最近的共同祖先节点,LCA的定义没什么好解释的,主要是这道题的解法。
38 0
Leetcode 623. Add One Row to Tree
题目很简单,在树的第d层加一层,值为v。递归增加一层就好了。代码如下
47 0
LeetCode contest 190 5418. 二叉树中的伪回文路径 Pseudo-Palindromic Paths in a Binary Tree
LeetCode contest 190 5418. 二叉树中的伪回文路径 Pseudo-Palindromic Paths in a Binary Tree
LeetCode Contest 178-1367. 二叉树中的列表 Linked List in Binary Tree
LeetCode Contest 178-1367. 二叉树中的列表 Linked List in Binary Tree
LeetCode 429. N-ary Tree Level Order Traversal
给定一个 N 叉树,返回其节点值的层序遍历。 (即从左到右,逐层遍历)。
86 0
LeetCode 429. N-ary Tree Level Order Traversal
|
Python
LeetCode 401. Binary Watch
二进制手表顶部有 4 个 LED 代表小时(0-11),底部的 6 个 LED 代表分钟(0-59)。 每个 LED 代表一个 0 或 1,最低位在右侧。
107 0
LeetCode 401. Binary Watch
|
算法 Python
LeetCode 108. 将有序数组转换为二叉搜索树 Convert Sorted Array to Binary Search Tree
LeetCode 108. 将有序数组转换为二叉搜索树 Convert Sorted Array to Binary Search Tree