Description

有一棵二叉树,其中所有节点的值都不一样,找到含有节点最多 的搜索二叉子树,并返回这棵子树的头节点.

给定二叉树的头结点root,请返回所求的头结点,若出现多个节点最多的子树,返回头结点权值最大的。

Solutions

1. Recursion

# -*- coding:utf-8 -*-
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
class MaxSubtree:
    def getMax(self, root):
        # write code here
        if not root:
            return None
        head, _, _, _ = self.getHelp(root)
        return head
    def getHelp(self, root):
        if not root:
            return None, 0, float('-inf'), float('inf')
        l_head,l_node,l_max,l_min = self.getHelp(root.left)
        r_head, r_node,r_max,r_min = self.getHelp(root.right)
        if l_head == root.left and r_head == root.right and l_max <root.val and r_min >root.val:
            return root, l_node+r_node+1, max(root.val,r_max), min(root.val, l_min)
        else:
            if l_node > r_node:
                res = l_head
                nodes = l_node
            else:
                res = r_head
                nodes = r_node
            return res, nodes, max(root.val,l_max,r_max), min(root.val,l_min,r_min)

References

  1. 7.14 最大二叉搜索子树