边工作边刷题：70天一遍leetcode: day 76

Count Univalue Subtrees

要点：检测条件比较有意思：因为可能的情况比较多，只要违反了任意一条就return False，所以可以只考虑False的情况，最后return True。

https://repl.it/CoqQ

错误点：这题类似Largest BST Subtree（with all descendants，bottom up方法，or post order），左子树不符合只能invalidate root，但仍然要recurse到右子树，所以不能提前返回，而是要在右子树访问完以后返回。

post-order iteration: 注意必须要用map记录，因为post-order没法从栈中获得当前结点左/右子树的情况，所以只能用map记录

https://repl.it/CopV

# 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 countUnivalSubtrees(self, root):

        """

        :type root: TreeNode

        :rtype: int

        """

        def helper(root):

            isUnival = True

            if root.left and (not helper(root.left) or root.val!=root.left.val):

                isUnival = False

            if root.right and (not helper(root.right) or root.val!=root.right.val):

                isUnival = False

            if not isUnival:

                return False

            #print root.val

            self.count+=1

            return True

        self.count=0

        if not root: return 0

        helper(root)

        return self.count

# Given a binary tree, count the number of uni-value subtrees.

# A Uni-value subtree means all nodes of the subtree have the same value.

# For example:

# Given binary tree,

#               5

#              / \

#             1   5

#           / \   \

#           5   5   5

# return 4.

# Hide Tags Tree

# 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 countUnivalSubtrees(self, root):

        """

        :type root: TreeNode

        :rtype: int

        """

        if not root: return 0

        stk = [root]

        umap = {}

        pre = None

        count = 0

        while stk:

            cur = stk[-1]

            if pre==None or pre.left==cur or pre.right==cur:

                if cur.left:

                    stk.append(cur.left)

                elif cur.right:

                    stk.append(cur.right)

            elif cur.left==pre:

                if cur.right:

                    stk.append(cur.right)

            else:

                stk.pop()

                if cur.left and (not umap[cur.left] or cur.left.val!=cur.val):

                    pre = cur

                    umap[cur]=False

                    continue

                if cur.right and (not umap[cur.right] or cur.right.val!=cur.val):

                    pre = cur

                    umap[cur]=False

                    continue

                umap[cur]=True

                count+=1

            pre = cur

        return count

巴特西

边工作边刷题：70天一遍leetcode: day 76

Count Univalue Subtrees

最新文章

热门文章