LeetCode刷题：二叉树和堆

关于二叉树和堆的 7 个必知必会的代码实现

二叉树

• 实现一个二叉查找树，并且支持插入、删除、查找操作

• 实现查找二叉查找树中某个节点的后继、前驱节点

• 实现二叉树前、中、后序以及按层遍历

堆

• 实现一个小顶堆、大顶堆、优先级队列

• 实现堆排序

• 利用优先级队列合并 K 个有序数组

• 求一组动态数据集合的最大 Top K

题目

Invert Binary Tree（翻转二叉树）

思路

后序遍历，交换左右结点即可

代码

public TreeNode invertTree(TreeNode root) {
    if (root == null) {
        return null;
    }
    invertTree(root.left);
    invertTree(root.right);
    TreeNode temp = root.left;
    root.left = root.right;
    root.right = temp;
    return root;
}

Maximum Depth of Binary Tree（二叉树的最大深度）

思路

深度优先遍历就可以得出树的深度

代码

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

Validate Binary Search Tree（验证二叉查找树）

思路

可以用递归法实现。首先将结点的值与上界和下界（如果有）比较。然后，对左子树和右子树递归进行该过程。

代码

public boolean isValidBST(TreeNode root) {
    return help(root, null, null);
}

private boolean help(TreeNode root, Integer lower, Integer upper) {
    if (root == null) {
        return true;
    }
    if (lower != null && root.val <= lower) {
        return false;
    }
    if (upper != null && root.val >= upper) {
        return false;
    }
    if (!help(root.left, lower, root.val)) {
        return false;
    }
    if (!help(root.right, root.val, upper)) {
        return false;
    }
    return true;
}

Path Sum（路径总和）

思路

如果当前节点不是叶子，对它的所有孩子节点，递归调用 hasPathSum 函数，其中 sum 值减去当前节点的权值；如果当前节点是叶子，检查 sum 值是否为 0，也就是是否找到了给定的目标和。

代码

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