leetcode-cn Daily Challenge on August 17th, 2020.
leetcode Daily Challenge on December 22th, 2020.
Difficulty : Easy
Related Topics : Tree、DFS
Given a binary tree, determine if it is height-balanced.
For this problem, a height-balanced binary tree is defined as:
a binary tree in which the left and right subtrees of every node differ in height by no more than 1.
Given the following tree [3,9,20,null,null,15,7]: 3 / \ 9 20 / \ 15 7 Return true.
Given the following tree [1,2,2,3,3,null,null,4,4]: 1 / \ 2 2 / \ 3 3 / \ 4 4 Return false.
- mine
- Java
- DFS
Runtime: 0 ms, faster than 100.00%, Memory Usage: 39.6 MB, less than 71.59% of Java online submissions
//O(N)time //O(D)space boolean res = true; public boolean isBalanced(TreeNode root) { dfs(root); return res; } int dfs(TreeNode node){ if(node == null || !res) return 0; int left = dfs(node.left); int right = dfs(node.right); if(Math.abs(left - right) > 1){ res = false; } return Math.max(left, right) + 1; }
- DFS
- Java