LEETCODE UNLOCK

LeetCode刷题:二叉树和堆

2019.09.05 13:54 0

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

二叉树

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

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

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

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

  • 实现堆排序

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

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

题目

Invert Binary Tree(翻转二叉树)

思路

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

代码

1
2
3
4
5
6
7
8
9
10
11
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(二叉树的最大深度)

思路

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

代码

1
2
3
4
5
6
7
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(验证二叉查找树)

思路

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

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
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,也就是是否找到了给定的目标和。

代码

1
2
3
4
5
6
7
8
9
10
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);
}

评论加载中