个人感觉学会这4个典例基本就算把初级树题刷完了(代码都参考了效率100%的)（主要是其中遍历手法）！So，Enjoy！
二叉树的所有路径(带父信息)
class Solution {
public List<String> binaryTreePaths(TreeNode root) {
List<String> res=new ArrayList<>(100);
dfs(root,"",res);
return res;
}
public void dfs(TreeNode root,String la,List<String> res){
if (root==null){
return;
}
StringBuilder sbu=new StringBuilder(la);
sbu.append(root.val);
if (root.left==null&&root.right==null){
res.add(sbu.toString());
}else{
sbu.append("->");
dfs(root.left,sbu.toString(),res);
dfs(root.right,sbu.toString(),res);
}
}
}
树直径 (展开与收缩)
public class DiameterOfBinaryTree {
int ans;
public int diameterOfBinaryTree(TreeNode root) {
ans = 1;
depth(root);
return ans - 1;
}
public int depth(TreeNode node) {
if (node == null) {
return 0; // 访问到空节点了，返回0
}
int L = depth(node.left); // 左儿子为根的子树的深度
int R = depth(node.right); // 右儿子为根的子树的深度
ans = Math.max(ans, L+R+1); // 计算d_node即L+R+1 并更新ans
return Math.max(L, R) + 1; // 返回该节点为根的子树的深度
}
}
二叉树的层平均值 (带层遍历)
class Solution {
public int getH(TreeNode root) {
if (root == null) {
return 0;
}
int left = 1 + getH(root.left);
int right = 1 + getH(root.right);
return Math.max(left, right);
}
public List<Double> averageOfLevels(TreeNode root) {
int h = getH(root);
long[] sums = new long[h];
int[] counts = new int[h];
dfs(root, 0, sums, counts);
List<Double> ret = new ArrayList<>(h);
for (int i = 0; i < h; i++) {
ret.add(1.0 * sums[i] / counts[i]);
}
return ret;
}
public void dfs(TreeNode root, int h, long[] sums, int[] counts) {
if (root == null) {
return;
}
sums[h] += root.val;
counts[h] += 1;
dfs(root.left, h + 1, sums, counts);
dfs(root.right, h + 1, sums, counts);
}
}
相同的树(两树同时遍历)
class Solution {
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);
}
}
