The largest binary search subtree of nowcoder


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.


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


# 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)
            lnode, lcount, lMaxNum, lMinNum = None, 0, 0, 0
        if root.right:
            rnode, rcount, rMaxNum, rMinNum = self.getNode(root.right)
            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
            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
                    return lnode, lcount, lMaxNum, lMinNum
                if root.val < rMinNum and rnode == root.right and lcount == 0:
                    return root, rcount + 1, rMaxNum, root.val
                    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