LeetCode - Easy - 110. Balanced Binary Tree

小灰灰 2022-12-28 09:05 133阅读 0赞

## Topic ##

*  Tree
 *  Depth-first Search
 *  Recursion

## Description ##

[https://leetcode.com/problems/balanced-binary-tree/][https_leetcode.com_problems_balanced-binary-tree]

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.

**Example 1**:

3
      / \
     9  20
       /  \
      15   7
    Input: root = [3,9,20,null,null,15,7]
    Output: true

**Example 2**:

1
           / \
          2   2
         / \
        3   3
       / \
      4   4
    Input: root = [1,2,2,3,3,null,null,4,4]
    Output: false

**Example 3**:

Input: root = []
    Output: true

**Constraints**:

*  The number of nodes in the tree is in the range \[0, 5000\].
 *  \-10⁴ <= Node.val <= 10⁴

## Analysis ##

**方法一：从上到下法(the top down approach)**。The first method checks whether the tree is balanced strictly according to the definition of balanced binary tree: the difference between the heights of the two sub trees are not bigger than 1, and both the left sub tree and right sub tree are also balanced.

For the current node root, calling height() for its left and right children actually has to access all of its children, thus the complexity is O(N). We do this for each node in the tree, so the overall complexity of isBalanced will be O(N^2). This is a top down approach.

--------------------

**方法二：从下而上法(the bottom up way)**。

The second method is based on DFS. Instead of calling height() explicitly for each child node, we return the height of the current node in DFS recursion. When the sub tree of the current node (inclusive) is balanced, the function dfsHeight() returns a non-negative value as the height. Otherwise -1 is returned. According to the leftHeight and rightHeight of the two children, the parent node could check if the sub tree is balanced, and decides its return value.

## Submission ##

import com.lun.util.BinaryTree.TreeNode;
    
    public class BalancedBinaryTree { 
    	
    	//方法一：从上到下法(the top down approach)
    	public boolean isBalanced1(TreeNode node) { 
    		if (node == null)
    			return true;
    		int leftHight = height1(node.left);
    		int rightHight = height1(node.right);
    		boolean balance = Math.abs(leftHight - rightHight) <= 1;
    		return balance && isBalanced1(node.left) && isBalanced1(node.right);
    	}
    
    	private int height1(TreeNode node) { 
    		return node == null ? 0 : Math.max(height1(node.left), height1(node.right)) + 1;
    	}
    
    	//方法二：从下而上法(the bottom up way)
    	public boolean isBalanced2(TreeNode node) { 
    		return height2(node) != -1;
    	}
    
    	private int height2(TreeNode node) { 
    		if (node == null)
    			return 0;
    
    		int leftHeight = height2(node.left);
    		if (leftHeight == -1)
    			return -1;
    
    		int rightHeight = height2(node.right);
    		if (rightHeight == -1)
    			return -1;
    
    		boolean balance = Math.abs(leftHeight - rightHeight) <= 1;
    
    		return balance ? Math.max(leftHeight, rightHeight) + 1 : -1;
    	}
    
    }

## Test ##

import static org.junit.Assert.*;
    import org.junit.Test;
    
    import com.lun.util.BinaryTree.TreeNode;
    
    public class BalancedBinaryTreeTest { 
    
    	@Test
    	public void test1() { 
    		BalancedBinaryTree obj = new BalancedBinaryTree();
    		TreeNode root = new TreeNode(3);
    		
    		root.left = new TreeNode(9);
    		root.right = new TreeNode(20);
    		
    		root.right.left = new TreeNode(15);
    		root.right.right = new TreeNode(7);
    		
    		assertTrue(obj.isBalanced1(root));
    		assertTrue(obj.isBalanced2(root));
    	}
    	
    	@Test
    	public void test2() { 
    		BalancedBinaryTree obj = new BalancedBinaryTree();
    		TreeNode root = new TreeNode(1);
    		
    		root.left = new TreeNode(2);
    		root.right = new TreeNode(2);
    		
    		root.left.left = new TreeNode(3);
    		root.left.right = new TreeNode(3);
    		
    		root.left.left.left = new TreeNode(4);
    		root.left.left.right = new TreeNode(4);
    
    		assertFalse(obj.isBalanced1(root));
    		assertFalse(obj.isBalanced2(root));
    	}
    	
    	@Test
    	public void test3() { 
    		BalancedBinaryTree obj = new BalancedBinaryTree();
    		TreeNode root = null;
    		
    		assertTrue(obj.isBalanced1(root));
    		assertTrue(obj.isBalanced2(root));
    	}
    	
    }

[https_leetcode.com_problems_balanced-binary-tree]: https://leetcode.com/problems/balanced-binary-tree/