The largest binary search subtree of nowcoder

subject

There is a binary tree in which the values of all nodes are different. Find the search binary tree with the most nodes, and return the head node of this subtree
Given the head node root of a binary tree, please return the head node. If there is a subtree with the most nodes, return the one with the largest weight of the head node.

thinking

Recursion. Find the head node of the search binary tree of a node's left subtree and right subtree respectively.

Code

# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
class MaxSubtree:
    def getNode(self, root):
        if root.left:
            lnode, lcount, lMaxNum, lMinNum = self.getNode(root.left)
        else:
            lnode, lcount, lMaxNum, lMinNum = None, 0, 0, 0
        if root.right:
            rnode, rcount, rMaxNum, rMinNum = self.getNode(root.right)
        else:
            rnode, rcount, rMaxNum, rMinNum = None, 0, 0, 0
        if lMaxNum < root.val and root.val < rMinNum and lnode == root.left and rnode == root.right:
            return root, lcount + rcount + 1, rMaxNum, lMinNum
        else:
            if lcount == 0 and rcount == 0:
                return root, 1, root.val, root.val
            if lcount > rcount:
                if lMaxNum < root.val and lnode == root.left and rcount == 0:
                    return root, lcount + 1, root.val, lMinNum
                else:
                    return lnode, lcount, lMaxNum, lMinNum
            else:
                if root.val < rMinNum and rnode == root.right and lcount == 0:
                    return root, rcount + 1, rMaxNum, root.val
                else:
                    return rnode, rcount, rMaxNum, rMinNum
    def getMax(self, root):
        # write code here
        node, count, maxNum, minNum = self.getNode(root)
        return node

Posted on Sat, 02 May 2020 04:52:11 -0700 by bills50000