二叉树，树的每个节点最多只能有两个子节点。
二叉树的操作主要有遍历、查找、删除等等。一棵树要么是空树，要么有两个指针，每个指针指向一棵树。树是一种递归结构，很多树的问题可以使用递归来处理。
LeetCode定义的二叉树结构：
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
1. 树的高度
104. Maximum Depth of Binary Tree (Easy)
思路：
利用递归，递归出口是root==null，最终返回左、右子树的最大值+1；
代码：
public int maxDepth(TreeNode root) {
if (root == null) {
return 0;
}
int l = maxDepth(root.left);
int r = maxDepth(root.right);
return Math.max(l, r) + 1;
}
2. 平衡树
110. Balanced Binary Tree (Easy)
Given the following tree [3,9,20,null,null,15,7]:
3
/ \
9 20
/ \
15 7
思路：
利用求解树的高度的方法，在求高度的同时，判断左右字数的高度是否大于1。
代码：
boolean isBalance = true;
public boolean isBalanced(TreeNode root) {
getDepth(root);
return isBalancel;
}
private int getDepth(TreeNode root) {
if (root == null) {
return 0;
}
int l = getDepth(root.left);
int r = getDepth(root.right);
// 大于1，则标志位置为false
if (Match.abs(l-r) > 1) {
isBalance = false;
}
return Math.max(l, r) + 1;
}
2.1 判断是否是查找二叉树
110. Balanced Binary Tree (Easy)
验证二叉搜索树
给定一个二叉树，判断其是否是一个有效的二叉搜索树。
假设一个二叉搜索树具有如下特征：
节点的左子树只包含小于当前节点的数。
节点的右子树只包含大于当前节点的数。
所有左子树和右子树自身必须也是二叉搜索树。
示例 1:
输入:
2
/ \
1 3
输出: true
示例 2:
输入:
5
/ \
1 4
/ \
3 6
输出: false
解释: 输入为: [5,1,4,null,null,3,6]。
根节点的值为 5 ，但是其右子节点值为 4 。
思路：
中序遍历展开二叉树，然后判断是否是有序序列。
代码：
private List<Integer> al = new ArrayList<>();
public boolean isValidBST(TreeNode root) {
inOrder(root);
for (int i = 0; i < al.size()-1; i++) {
if (al.get(i) >= al.get(i+1)) {
return false;
}
}
return true;
}
private void inOrder(TreeNode root) {
if (root != null) {
inOrder(root.left);
al.add(root.val);
inOrder(root.right);
}
}
3. 两节点的最长路径
543. Diameter of Binary Tree (Easy)
给定一棵二叉树，你需要计算它的直径长度。
一棵二叉树的直径长度是任意两个结点路径长度中的最大值。这条路径可能穿过根结点。
示例 :
给定二叉树
1
/ \
2 3
/ \
4 5
返回 3, 它的长度是路径 [4,2,1,3] 或者 [5,2,1,3]。
注意：两结点之间的路径长度是以它们之间边的数目表示。
思路：
还是利用树的高度的方法，在求高度的同时，计算l+r的最大值。
代码：
private int max = 0;
public int diameterOfBinaryTree(TreeNode root) {
getDepth(root);
return max;
}
private int getDepth(TreeNode root) {
if (root == null) {
return 0;
}
int l = getDepth(root.left);
int r = getDepth(root.right);
// 左右子树加起来的最大值
max = Math.max(l+r, max);
return Math.max(l, r) + 1;
}
4. 翻转树
226. Invert Binary Tree (Easy)
翻转一棵二叉树。
示例：
输入：
4
/ \
2 7
/ \ / \
1 3 6 9
输出：
4
/ \
7 2
/ \ / \
9 6 3 1
思路：
利用递归的原理，交换root的左右子树，交换前要先保存。
代码：
public TreeNode invertTree(TreeNode root) {
if (root == null) {
return null;
}
TreeNode left = root.left;
root.left = invertTree(root.right);
root.right = invertTree(left);
return root;
}
5. 归并两棵树
617. Merge Two Binary Trees (Easy)
给定两个二叉树，想象当你将它们中的一个覆盖到另一个上时，两个二叉树的一些节点便会重叠。
你需要将他们合并为一个新的二叉树。
合并的规则是如果两个节点重叠，那么将他们的值相加作为节点合并后的新值，
否则不为 NULL 的节点将直接作为新二叉树的节点。
Input:
Tree 1 Tree 2
1 2
/ \ / \
3 2 1 3
/ \ \
5 4 7
Output:
3
/ \
4 5
/ \ \
5 4 7
思路：
此问题比较简单，直接合并即可
代码：
public TreeNode mergeTrees(TreeNode t1, TreeNode t2) {
if (t1 == null) {
return t2;
}
if (t2 == null) {
return t1;
}
TreeNode root = new TreeNode(t1.val + t2.val);
root.left = mergeTrees(t1.left, t2.left);
root.right = mergeTrees(t1.right, t2.right);
return root;
}
6. 判断路径和是否等于一个数
Leetcdoe : 112. Path Sum (Easy)
给定一个二叉树和一个目标和，判断该树中是否存在根节点到叶子节点的路径，
这条路径上所有节点值相加等于目标和。
说明: 叶子节点是指没有子节点的节点。
示例:
给定如下二叉树，以及目标和 sum = 22，
5
/ \
4 8
/ / \
11 13 4
/ \ \
7 2 1
返回 true, 因为存在目标和为 22 的根节点到叶子节点的路径 5->4->11->2。
思路：
递归处理，每一轮递归都判断当前val与sum是否相等，递归时传入的是sum-root.val
代码：
public boolean hasPathSum(TreeNode root, int sum) {
if (root == null) {
return false;
}
if (root.left == null && root.right == null && root.val == sum) {
return true;
}
return hasPathSum(root.left, sum - root.val)
|| hasPathSum(root.right, sum - root.val);
}
