二叉树

概述

二叉树主要考察满二叉树和完全二叉树,

可以用来解决问题的方法:

涉及到二叉树的构造:先序遍历

求普通二叉树的属性:后序遍历,单纯求深度就用前序

求二叉搜索树的属性:中序遍历

递归

确定递归函数的参数和返回值

确定终止条件

确定单层递归的逻辑

问题类型:

二叉树的最近公共祖先

Q:给定一个二叉树, 找到该树中两个指定节点的最近公共祖先

输入：root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 1
输出：3

关键点

递归

private boolean dfs(TreeNode root, TreeNode p, TreeNode q) {
    if (root == null) return false;//定义出口
    boolean lson = dfs(root.left, p, q);
    boolean rson = dfs(root.right, p, q);
    if ((lson && rson) || ((root.val == p.val || root.val == q.val) && (lson || rson))) {
        ans = root;
    } 
    return lson || rson || (root.val == p.val || root.val == q.val);
}
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
    this.dfs(root, p, q);
    return this.ans;
}

二叉树的最小深度

Q:给定一个二叉树，找出其最小深度

输入：root = [3,9,20,null,null,15,7]
输出：2

关键点

递归

public int minDepth(TreeNode root) {
    if (root == null) {
        return 0;
    }
    if (root.left == null && root.right == null) {
        return 1;
    }
    int min_depth = Integer.MAX_VALUE;
    if (root.left != null) {
        min_depth = Math.min(minDepth(root.left), min_depth);
    }
    if (root.right != null) {
        min_depth = Math.min(minDepth(root.right), min_depth);
    }
    return min_depth + 1;
}