Leo Lei | 雷雨
August 06, 2018
Check if a binary tree is balanced
Balanced Binary Tree: a binary tree in which the depth of the two subtrees of every node never differ by more than 1.
https://www.youtube.com/watch?v=TWDigbwxuB4
The problem is harder than it appears even it's marked as easy on Leetcode.
The brute-force way would be getting the depths of the left and right subtrees for each node. (see LeetCode 104. Maximum Depth of Binary Tree) The time would be O(n2) cause for each node, it takes O(n) to check the depth.
Since there are lots of overlaps of the subproblems, dynamic programming could be used here. For example, the heights of the smaller subtrees can be used to built up the heights of the larger subtrees.(TODO: implement this)
Below is a solution that tackles the problem in a post-traversal way.
class Solution:
def isBalanced(self, root):
"""
:type root: TreeNode
:rtype: bool
"""
def helper(root):
if not root:
return 0
lh = helper(root.left)
if lh == -1:
return -1
rh = helper(root.right)
if rh == -1:
return -1
if abs(lh - rh) > 1:
return -1
return 1 + max(lh, rh)
res = helper(root)
return res != -1The SecOps Playbook - How SecOps Enables Secure Code Release At Scale and At Speed
Some good tips on building up SecOps team/culture
Gauntlt is a ruggedization framework that enables security testing that is usable by devs, ops and security.