**104. 二叉树的最大深度（入门）**

class Solution {
    public int maxDepth(TreeNode root) {
        if(root == null) return 0;
        return Math.max(maxDepth(root.left), maxDepth(root.right)) + 1; 
    }
}

**872. 叶子相似的树（DFS）**

class Solution {
		// 得到一个树的叶子序列
    public void getLeaf(TreeNode root, ArrayList<Integer> l) {
        if(root.left == null && root.right == null) {
            l.add(root.val);
        }
        if(root.left != null) getLeaf(root.left, l);
        if(root.right != null) getLeaf(root.right, l);
    }
    public boolean leafSimilar(TreeNode root1, TreeNode root2) {
        ArrayList<Integer> l1 = new ArrayList<>();
        ArrayList<Integer> l2 = new ArrayList<>();
        getLeaf(root1, l1);
        getLeaf(root2, l2);
        if(l1.size() != l2.size()) return false;

        for(int i = 0; i < l1.size(); i++) {
            if(l1.get(i) != l2.get(i)) return false;
        }
        return true;
    }
}

**1448. 统计二叉树中好节点的数目（DFS搜索）**

class Solution {
    int ans;
    public void dfs(TreeNode root, int max) {
        if(root == null) return ;
        
        // 判断是不是以root为终点的最大结点，也就是好节点
        if(root.val >= max) {
            ans++;
            max = root.val;    
        }
        dfs(root.left, max);
        dfs(root.right, max);
    }
    public int goodNodes(TreeNode root) {
        dfs(root, root.val);
        return ans;
    }
}

**437. 路径总和 III（暴搜DFS or ）**

暴力搜索

class Solution {
    // 暴力搜索以root为起点的符合条件的路径数量
    public int dfs(TreeNode root, long targetSum) {
        if(root == null) return 0;
        int sum = 0;
        if(root.val == targetSum) sum++;
        
        sum += dfs(root.left, targetSum - root.val);
        sum += dfs(root.right, targetSum - root.val);
        return sum;
    }
    public int pathSum(TreeNode root, long targetSum) {
        if(root == null) return 0;
        int res = 0;
        res += dfs(root, targetSum);
        res += pathSum(root.left, targetSum);
        res += pathSum(root.right, targetSum);
        return res;
    }
}

树上前缀和

class Solution {
    Map<Long, Integer> prefix = new HashMap<Long, Integer>();
    public int pathSum(TreeNode root, int targetSum) {
        prefix.put(0L, 1);
        return dfs(root, 0, targetSum);
    }
    public int dfs(TreeNode root, long curr, int targetSum) {
            if(root == null) return 0;
            curr += root.val;
            // 以当前节点为结尾，且路径总和为curr有x条
            prefix.put(curr, prefix.getOrDefault(curr, 0) + 1);

            int ret = 0;
            // 以当前节点为结尾，路径总和为curr - targetSum的条数，比如当前前缀和是18
            // 我就找前缀和有没有18-8=10的路径，如有x条，则以当前为结尾的就是x条。
            ret = prefix.getOrDefault(curr - targetSum, 0);
            
            ret += dfs(root.left, curr, targetSum);
            ret += dfs(root.right, curr, targetSum);
						
						// 删除过期的前缀和
            prefix.put(curr, prefix.getOrDefault(curr , 0) - 1);
            return ret;
    }
}

**1372. 二叉树中的最长交错路径（记忆化搜索 or 树上dp）**

DP解法

class Solution {
    // 以TreeNode为终点，而且最后一个是右结点的 最大路径
    Map<TreeNode, Integer> right = new HashMap<>();
    Map<TreeNode, Integer> left = new HashMap<>();
    // BFS遍历
    Queue<TreeNode[]> q = new LinkedList<>();

    public int longestZigZag(TreeNode root) {
        dp(root);
        int maxAns = 0;
        for (TreeNode u : right.keySet()) {
            maxAns = Math.max(maxAns, Math.max(right.get(u), left.get(u)));
        }
        return maxAns;

    }
    public void dp(TreeNode o) {
        q.offer(new TreeNode[]{o, null});
        while(!q.isEmpty()) {
            TreeNode[] front = q.poll();
            TreeNode cur = front[0], parent = front[1];
            right.put(cur, 0);
            left.put(cur, 0);
            // 如果有
            if(parent != null) {
                // 父亲的左节点为当前节点，  right[cur] = left.get(parent) + 1
                if(parent.left == cur) right.put(cur, left.get(parent) + 1);
                if(parent.right == cur) left.put(cur, right.get(parent) + 1);
            }
            if(cur.left != null) q.offer(new TreeNode[]{cur.left, cur});
            if(cur.right != null) q.offer(new TreeNode[]{cur.right, cur});
        }
    }
}

记忆化搜索