LeetCode-110:Balanced Binary Tree

¶Balanced Binary Tree

¶Problem Describe:

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
the input : [ 3,9,20,null.null,15,7 ]
1
2
3
4
5
3
/ \
9 20
/ \
15 7
return true

the input:[1,2,2,3,3,null,null,4,4]

return false

¶Answer–Java Version

top-down：


//the definition of a treeNode
static class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;

    TreeNode() {
    }

    TreeNode(int val) {
        this.val = val;
    }

    TreeNode(int val, TreeNode left, TreeNode right) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}

public static boolean isBlanacedTree(TreeNode root) {
	//with a null treeNode ,it has two null sub-node also
    if (null == root) {
        return true;
    }
    TreeNode left = root.left;
    TreeNode right = root.right;
    //the first condition is the sub-tree height differ no more than 1
    //the second condition is all the sub-tree of a balanced-tree must a balanced-tree too
    return Math.abs(treeHeight(left) - treeHeight(right)) <= 1  && isBlanacedTree(left) && isBlanacedTree(right);
}

private static int treeHeight(TreeNode root) {

    //null treeNode got no height
    if (null == root) {
        return 0;
    } else {
        //in the other situation the tree height is at leart  one  
        return 1 + Math.max(treeHeight(root.left),treeHeight(root.right));
    }

}

this is the way to search a tree by top-down , as what we have already know at first , the most import way th slove an recursive problem is to find the min answer of this problem and try to understand the relation between the top question and it`s sub question
so for this problem ,there`re two condition we need to understand :
1. **The node of height-balanced tree differ in height no more than 1 **
2. **every sub-tree of balanced tree must be an balanced tree also **
under those two conditions we could translate it to code:
1. Math.abs(treeHeight(root.left) - treeHeight(right))<=1
2. isBalancedTree(root.left) && isBalancedTree(right)

¶Answer-go version

top-down:


package main

import "fmt"
import "math"

//the go struct of a treeNode,
//but in go lang,have no the concept of construct-method
//instead of return the object by a normal method of just defined directly
type treeNode struct{
	value int32 
	left *treeNode 
	right *treeNode 
}

func getTreeNode(value int32,left *treeNode,right *treeNode) treeNode{
	return treeNode{
		value : value,
		left : left ,
		right :right,
	}
}

func isBalancedTree(root *treeNode) bool{
	var flag bool=false
	if(nil == root){
		flag = true;
	}else{
		left := root.left
		right := root.right
		flag = (math.Abs(treeHeight(left) - treeHeight(right)) <= 1 &&  isBalancedTree(left) && isBalancedTree(right))
	}
	return flag
}

func treeHeight(root *treeNode)float64{

	var height float64
	var maxHeight float64 = 0
	if(nil == root){
		height = 0
	}else{
		var left  *treeNode = root.left
		var right *treeNode = root.right
		if(treeHeight(left) > treeHeight(right)){
			maxHeight =  treeHeight(left)
		}else{
			maxHeight =  treeHeight(right)
		}
	}
	return height + maxHeight
}

func main()  {
	
    //define the treeNodes
	ll := &treeNode{
		value : 4,
		left:nil,
		right:nil,
	}

	rr := &treeNode{
		value : 4,
		left:nil,
		right:nil,
	}

	left := &treeNode{
		value : 3,
		left:ll,
		right:nil,
	}

	right := &treeNode{
		value : 3,
		left:nil,
		right:rr,
	} 

	root := &treeNode{
		value : 2,
		left:left,
		right:right,
	}

	var result = isBalancedTree(root)
	fmt.Printf("isBalancedTree ? \t %T [%v]\n" ,result,result)
}

try to learn go lang by slove this kind of algorithm problem
**go basic **
1. go lang have no construct-method of an object , instead of the normal method to return the target object
2. **while define the object or the object-paramer of a method ,it should be ** like this : * treeNode , which means the Point of an object

//TODO