Binary Tree: 0到2个子节点;
Binary Search Tree: 所有左边的子节点 < node自身 < 所有右边的子节点；
1. Full类型： 除最下面一层外， 每一层都有两个子节点；
2. Complete类型： 除最下面一层外为Full类型， 但是最下面一层最所有子节点靠左；
3. Balanced类型： 左右两个子树的长度相差小于等于一；
/**
* Definition of TreeNode:
* public class TreeNode {
* public int val;
* public TreeNode left, right;
* public TreeNode(int val) {
* this.val = val;
* this.left = this.right = null;
* }
* }
*/
public class Solution {
/**
* @param root: The root of binary tree.
* @return: True if this Binary tree is Balanced, or false.
*/
int checkHeight(TreeNode root){
if(root == null) return -; int leftHeight = checkHeight(root.left);
if(leftHeight == Integer.MIN_VALUE) return Integer.MIN_VALUE; int rightHeight = checkHeight(root.right);
if(rightHeight == Integer.MIN_VALUE) return Integer.MIN_VALUE; int heightDiff = leftHeight - rightHeight;
if(Math.abs(heightDiff) > ){
return Integer.MIN_VALUE;
}else{
return Math.max(leftHeight, rightHeight) + ;
}
}
public boolean isBalanced(TreeNode root) {
return checkHeight(root) != Integer.MIN_VALUE; // write your code here
}
}
traverse： 遍历； recursion： 递归（反复用自身）； iteration： 迭代（循环）；
3种遍历：
1. inorder： 左， node自身， 右（最左下角的node为第一个， 最右下角的node为最后一个）；
2. preorder： node自身， 左， 右（node自身为第一个， 最右下角的node为最后一个）；
3. postorder： 左， 右， node自身（最左下角的node为第一个， node自身为最后一个）；
class Node {
int val;
Node left;
Node right;
public Node(int v) {
this.val = v;
}
}
public class BST {
public static void inorder(Node node) {
// 1. return condition
if(node == null) return;
// 2. process
inorder(node.left);
System.out.println(node.val);
inorder(node.right);
}
public static void preorder(Node node) {
if(node == null) return;
System.out.println(node.val);
preorder(node.left);
preorder(node.right);
}
public static void postorder(Node node) {
if(node == null) return;
postorder(node.left);
postorder(node.right);
System.out.println(node.val);
}
public static void main(String[] args) {
// TODO Auto-generated method stub
Node root = buildTree();
inorder(root);
}
public static Node buildTree() {
Node ten = new Node();
Node one = new Node();
Node fifteen = new Node();
Node five = new Node();
five.left = one;
ten.left = five;
ten.right = fifteen;
return ten;
}
}