二叉树定义
<pre>
/**
- Definition for a binary tree node.
- public class TreeNode {
int val;TreeNode left;TreeNode right;TreeNode(int x) { val = x; }- }
*/
</pre>
</br>
1. 二叉树的遍历
分广度优先遍历（层序遍历）和深度优先遍历。
</br>
层序遍历（level order）
例如
<pre>
3
/
9 20
/
15 7
</pre>
返回
<pre>
[
[3],
[9,20],
[15,7]
]
</pre>
代码如下：
<pre>
public List<List<Integer>> levelOrder(TreeNode root) {
List<List<Integer>> list = new ArrayList<List<Integer>>();
if(root == null) return list;
Queue<TreeNode> queue = new LinkedList<TreeNode>();
queue.offer(root);
while(!queue.isEmpty()){
int num = queue.size();
List<Integer> levelNodes = new ArrayList<Integer>();
for(int i = 0; i < num; i++){
TreeNode temp = queue.poll();
levelNodes.add(temp.val);
if(temp.left != null) queue.offer(temp.left);
if(temp.right != null ) queue.offer(temp.right);
}
list.add(levelNodes);
}
return list;
}
</pre>
</br>
深度优先遍历分前序（preorder）、中序（inorder）、后序（postorder），前中后是指root被访问的相对次序。代码就只用前序举例了。
<pre>
public void preorder(TreeNode root){
if(root == null) return;
visit(root);
preorder(root.left);
preorder(root.right);
}
</pre>
</br>
2.比较两棵树是否相同
<pre>
public boolean isSameTree(TreeNode p, TreeNode q) {
if(p == null && q == null) return true;
if(p == null || q == null) return false;
if(p.val != q.val) return false;
return isSameTree(p.left, q.left) && isSameTree(p.right, q.right);
}
</pre>
</br>
3.是否是平衡二叉树
平衡二叉树的定义：它是一棵空树或它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树。
这里用算高度的函数辅助判断。自己实现的时候发现有一些陷阱，也正说明了自己对递归还是理解得不透彻。
<pre>
public boolean isBalanced(TreeNode root) {
if(root == null) return true;
return getHeight(root) != -1;
}
public int getHeight(TreeNode root){
if(root == null) return 0;
int leftHeight = getHeight(root.left);
int rightHeight = getHeight(root.right);
if(leftHeight == -1) return -1;
if(rightHeight == -1) return -1;
if(Math.abs(leftHeight - rightHeight) > 1) return -1;
return Math.max(leftHeight, rightHeight) + 1;
}
</pre>
</br>
4.是否是完全二叉树
完全二叉树定义：除最后一层外，其它各层的结点数都达到最大个数，最后一层有叶子结点，并且叶子结点都是从左到右依次排布，这就是完全二叉树。
容易想到要用到广度优先遍历。???
</br>
5.两节点最低公共祖先
BST的话很简单，充分利用BST特性，从root开始找一个处于两节点值中间的一个节点。
<pre>
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
if(root.val > p.val && root.val > q.val) return lowestCommonAncestor(root.left,p,q);
if(root.val < p.val && root.val < q.val) return lowestCommonAncestor(root.right,p,q);
return root;
}
</pre>
一般的二叉树的话，还没想明白，先把leetcode上一个答案粘在这吧。
<pre>
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
if(root == null) return null;
if(root == p || root == q) return root;
TreeNode left = lowestCommonAncestor(root.left, p, q);
TreeNode right = lowestCommonAncestor(root.right, p, q);
return left != null && right != null ? root : left == null ? right : left;
}
</pre>
</br>
6. 前序中序构造后序
注意可以通过前序中提取出当前root，并在中序中找到root把中序分为左右两颗子树。还要注意此时前序也可以根据中序中root的位置确定左右分界，左/右的第一个数又是左/右子树的root。
<pre>
public TreeNode buildTree(int[] preorder, int[] inorder) {
return treeBuilder(preorder, inorder, 0, inorder.length, 0);
}
</br>
public TreeNode treeBuilder(int[] preorder, int[] inorder, int inStart, int inEnd, int preStart){
if(inorder == null || inorder.length == 0 || inStart >= inEnd) return null;
TreeNode root = new TreeNode(preorder[preStart]);
int index;
for(index = inStart; index < inEnd; index++){
if(preorder[preStart] == inorder[index]){
break;
}
}
root.left = treeBuilder(preorder, inorder, inStart, index, preStart + 1);
root.right = treeBuilder(preorder, inorder, index+1, inEnd, preStart + index - inStart + 1);
return root;
}
</pre>
