LintCode: Binary Tree Maximum Node

Binary Tree Maximum Node



Similar Problems:


Follow-up: 
- Assume we can't use global variable
- I want to return all max nodes
- I want to return the last max node
- I want to return the second max node, if we have. Otherwise return the first max node

Description

Find the maximum node in a binary tree, return the node.

Example

Given a binary tree:

     1
   /   \
 -5     2
 / \   /  \
0   3 -4  -5 
return the node with value 3.

Github: code.dennyzhang.com

Credits To: lintcode.com

Leave me comments, if you have better ways to solve.


  • Solution: With sub-function
## Blog link: https://code.dennyzhang.com/binary-tree-maximum-node
## Basic Ideas: any tree traversal
## Here we use pre-order
## Complexity: Time O(n), Space O(h)
"""
Definition of TreeNode:
class TreeNode:
    def __init__(self, val):
        self.val = val
        self.left, self.right = None, None
"""
class Solution:
    """
    @param: root: the root of tree
    @return: the max node
    """
    def maxNode(self, root):
        def dfs(root, maxNode):
            if root is None: return maxNode
            if root.val > maxNode.val: maxNode = root
            maxNode = dfs(root.left, maxNode)
            maxNode = dfs(root.right, maxNode)
            return maxNode
        return dfs(root, root)

  • Solution: Without sub-function
## Blog link: https://code.dennyzhang.com/binary-tree-maximum-node
## Basic Ideas: any tree traversal
## Here we use pre-order
## Complexity: Time O(n), Space O(h)
"""
Definition of TreeNode:
class TreeNode:
    def __init__(self, val):
        self.val = val
        self.left, self.right = None, None
"""
class Solution:
    """
    @param: root: the root of tree
    @return: the max node
    """
    def maxNode(self, root):
        if root is None: return root

        res = root
        if root.left:
            p = self.maxNode(root.left)
            if p.val > res.val: res = p

        if root.right:
            p = self.maxNode(root.right)
            if p.val > res.val: res = p
        return res
linkedin
github
slack

Share It, If You Like It.

Leave a Reply

Your email address will not be published.