Question: https://oj.leetcode.com/problems/balanced-binary-tree/
Question Name: Balanced Binary Tree
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 | # Definition for a binary tree node # class TreeNode: # def __init__(self, x): # self.val = x # self.left = None # self.right = None class Solution: # @param root, a tree node # @return a tuple, to say result. result[0] indicates whether the # subtree, with "current" being the root, is balanced. # result[1] is -1 if the substree is not balanced, or # otherwise the height of this subtree. def isBalancedHelper(self, current): if current == None: return (True, 0) else: # Check its left subtree left = self.isBalancedHelper(current.left) if left[0] == False: return (False, -1) # Check its right subtree right = self.isBalancedHelper(current.right) if right[0] == False: return (False, -1) # Check whether the depth of the two subtrees differ by # more than 1. if abs(left[1] - right[1]) <= 1: height = max(left[1], right[1]) + 1 return (True, height) else: return (False, -1) # @param root, a tree node # @return a boolean def isBalanced(self, root): return self.isBalancedHelper(root)[0] |
isn’t the requirement just to return a bool ?
ISBALANCED ; return True
is NOTBALANCED ; return False
this program returns a tuple from the Helper functions , and the main function is returning zero’th index element of the tuple. Couldnt we simplify this ?
Yes, it is possible to simply the return value. Anyway, the return value of helper should contain two pieces of information:
1. Whether this (sub)tree is balanced. (Here, we use the first item to represent it.)
2. If it is balanced, what is the height? (We use the second item to hold it)
However, the main function only need the first information.
An alternative solution is to return -1 if it is not balanced, or height otherwise.