aboutsummaryrefslogtreecommitdiff
path: root/balanced_binary_tree.py
diff options
context:
space:
mode:
authorJack Sangdahl <[email protected]>2025-02-25 23:03:17 -0700
committerJack Sangdahl <[email protected]>2025-02-25 23:03:17 -0700
commite8c16bee275788caf61d61fe641864fdb69447a9 (patch)
treeff7ddaf343cd33cdf8c0aec8687cc56d8d905246 /balanced_binary_tree.py
parent5afeed9d77e479ea3b576ff0c10b0d5f001cc078 (diff)
downloadleetcode-e8c16bee275788caf61d61fe641864fdb69447a9.tar.gz
leetcode-e8c16bee275788caf61d61fe641864fdb69447a9.zip
110. balanced binary tree
Diffstat (limited to 'balanced_binary_tree.py')
-rw-r--r--balanced_binary_tree.py34
1 files changed, 34 insertions, 0 deletions
diff --git a/balanced_binary_tree.py b/balanced_binary_tree.py
new file mode 100644
index 0000000..a677b56
--- /dev/null
+++ b/balanced_binary_tree.py
@@ -0,0 +1,34 @@
+# 110. Balanced Binary Tree
+import leetcode
+
+"""
+given a binary tree, determine if it is height balanced
+"""
+
+
+class Solution(object):
+ def isBalanced(self, root):
+ """
+ :type root: Optional[TreeNode]
+ :rtype: bool
+ """
+ self.balanced = True
+
+ def dfs(node):
+ if not node:
+ return 0
+ l, r = dfs(node.left), dfs(node.right)
+ if abs(l - r) > 1:
+ self.balanced = False
+ return max(l, r) + 1
+
+ dfs(root)
+ return self.balanced
+
+
+if __name__ == "__main__":
+ obj = Solution()
+ r1 = leetcode.treenode_build(vals=[3, 9, 20, None, None, 15, 7])
+ r2 = leetcode.treenode_build(vals=[1, 2, 2, 3, 3, None, None, 4, 4])
+ print(obj.isBalanced(r1))
+ print(obj.isBalanced(r2))