LeetCode-DFS-树类-简单难度

关于二叉树的相关深度优先遍历类题目，重点在于掌握最基本的前中后序遍历，大多数题目都在围绕这套逻辑，找到处理节点的时机，以及停止遍历的条件，即可顺利完成。

二叉树前中后序遍历模板

所谓前中后序，指的就是访问节点的时机。

前序：访问当前节点->左子树->右子树

中序：左子树->访问当前节点->右子树

后序：左子树->右子树->访问当前节点

public void dfs(TreeNode root) {
    // 最终终止条件，彻底遍历完了
    if (root == null) {
        return;
    }
    // 前序 System.out.println(root.val);
    dfs(root.left);
    // 中序 System.out.println(root.val);
    dfs(root.right);
    // 后序 System.out.println(root.val);
}

下面来几道练习

1. 二叉树的最大深度

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

2. 二叉树的最小深度

1.如果左右子树都为空，则返回1。

2.优先遍历左右子树，如果左子树为空，则返回右子树的深度，如果右子树为空，则返回左子树的深度。

3.如果都不为空，则返回二者较小的一个。

能走到第2步则表示左右子树至少有一个是非空的，而最小深度只能从非空的子树中产生，所以左右子树哪个不是空，就找它，如果都不是空，就找最小的。

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

3. 路径总和

基于先序遍历进行处理即可，目标是将targetSum减到0同时满足当前为叶子节点。

public boolean hasPathSum(TreeNode root, int targetSum) {
    if(root == null){
        return false;
    }
    int x = targetSum - root.val;
    if(root.left == null && root.right == null && x == 0){
        return true;
    }
    return hasPathSum(root.left, x) || hasPathSum(root.right, x);
}

4. 二叉树的最近公共祖先

1.当前遍历到的节点是空，或者是p本身、或者是q本身，则应当返回当前节点

2.优先遍历左右子树

3.如果左右子树都不为空，则root自然就是它们的最近公共祖先，因此直接返回root

4.除此之外，如果左子树为空，则最近公共祖先一定在右子树中，否则就在右子树中

public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
    if(root == null || root == p || root == q){
        return root;
    }
    TreeNode left = lowestCommonAncestor(root.left, p, q);
    TreeNode right = lowestCommonAncestor(root.right, p, q);
    if(left != null && right != null){
        return root;
    }
    return left != null ? left : right;
}

本题基于后序遍历进行处理，终止条件为当前节点为空，或者当前节点就是目标节点，所以如果左右子树都有返回值，则说明各自都找到目标节点，那最近公共祖先自然就是当前root节点。反之，如果左右子树都返回了空，则说明都没找到，那随便返回哪个都一样（因为无论哪个都是空）。另一类情况就是一个为空，一个不为空，言下之意就是，一个找到了目标值，一个未找到目标值，那自然得返回找到目标值的那一个，最后递归逻辑会带着其中一个返回的目标值，与另一个带着其中一个返回的目标值，命中左右子树都不为空的条件，即可返回root。

5. 求根节点到叶节点数字之和

这题直接按照先序遍历的方式，根据当前节点的值先进行计算，如果当前节点是叶子节点，则直接返回计算结果，否则将计算结果带入左右子树继续计算。

public int sumNumbers(TreeNode root) {
    return dfs(root, 0);
}
public int dfs(TreeNode root, int sum){
    if(root == null){
        return 0;
    }
    int x = sum * 10 + root.val;
    if(root.left == null && root.right == null){
        return x;
    }
    return dfs(root.left, x) + dfs(root.right, x);
}

6. 二叉搜索树中第K小的元素

对于二叉搜索树，只需要按照中序遍历，即可从小到大进行输出，所以找到第K小的元素，实际上就是返回第K次访问的元素即可。

int cnt = 0;
int ans = -1;
public int kthSmallest(TreeNode root, int k) {
    dfs(root, k);
    return ans;
}
public void dfs(TreeNode root, int k){
    if(root == null || ans != -1){
        return;
    }
    dfs(root.left, k);
    if(++cnt == k){
        ans = root.val;
        return;
    }
    dfs(root.right, k);
}