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
## 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
## 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
