LeetCode刷题:二叉树和堆

本文最后更新于:6 个月前

关于二叉树和堆的 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);
}

本博客所有文章除特别声明外,均采用 CC BY-SA 4.0 协议 ,转载请注明出处!