数据结构-LeetCode树相关题目

LeetCode–与树相关常见题目解题思路

递归解决

翻转二叉树

题目:翻转一棵二叉树。

1
2
3
4
5
     4
/ \
2 7
/ \ / \
1 3 6 9

输出:

1
2
3
4
5
     4
/ \
7 2
/ \ / \
9 6 3 1

分析

如标题所示,翻转二叉树可以使用递归:

  • 如果是空树,则返回null
  • 如果带有左右子树,则左子树换成右子树、右子树换成左子树。

代码

1
2
3
4
5
6
7
8
9
10
11
class Solution {
public TreeNode invertTree(TreeNode root) {
if(root==null) return null;
TreeNode left = root.left;
root.left = root.right;
root.right = left;
invertTree(root.right);
invertTree(root.left);
return root;
}
}

合并二叉树

题目:给定两个二叉树,想象当你将它们中的一个覆盖到另一个上时,两个二叉树的一些节点便会重叠。你需要将他们合并为一个新的二叉树。合并的规则是如果两个节点重叠,那么将他们的值相加作为节点合并后的新值,否则不为 NULL 的节点将直接作为新二叉树的节点。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
输入: 
Tree 1 Tree 2
1 2
/ \ / \
3 2 1 3
/ \ \
5 4 7
输出:
合并后的树:
3
/ \
4 5
/ \ \
5 4 7

注意: 合并必须从两个树的根节点开始。

分析

在一棵树(Tree 1)的基础上添加另一棵树(Tree 2)。

如果两树节点都不存在,返回null;

如果两树节点都存在,则将树1的根节点的数值相加;

如果树1节点存在,树2节点不存在,则不做操作;

如果树2节点存在,树1节点不存在,则将该结点插入树1中(如何插入??? )

不如换个思路?

用两棵树(Tree 1、Tree 2)的数据构成一棵新的树。

如果两树节点都不存在,返回null

如果树1节点存在,树2节点不存在,则返回树1(此后也不必再考虑);

如果树2节点存在,树1节点不存在,则返回树2;

如果树1、树2节点都存在,则新建一个节点,将树1+树2数据放入;

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public TreeNode mergeTrees(TreeNode t1, TreeNode t2) {
if(t1==null&&t2==null){
return null;
}
else if(t2==null){
return t1;
}
else if(t1==null){
return t2;
}
else{
TreeNode root = new TreeNode(t1.val + t2.val);
root.left = mergeTrees(t1.left,t2.left);
root.right = mergeTrees(t1.right,t2.right);
return root;
}
}
}

路经总和

注意看清题意!!!

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
//会传入根节点和数字22
public boolean hasPathSum(TreeNode root, int sum) {
if(root==null) {
return false;
}
if(root.left==null&&root.right==null) {
if(sum==root.val) return true;
else return false;
}
boolean a = hasPathSum(root.left,sum-root.val);
boolean b = hasPathSum(root.right,sum-root.val);
return a||b;
}
}

层次遍历

二叉树的层平均值

该题目的主要解决方法为先了解什么是层次遍历,这道题的主要思想就是新建一个队列用来存放一层的数值和,等该层全部加完之后统一处理,算其平均值。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
class Solution {
public List<Double> averageOfLevels(TreeNode root) {
List<Double> en = new ArrayList<>();
if(root==null) return en;
Queue<TreeNode> q = new LinkedList<>();
Queue<TreeNode> a = new LinkedList<>();
q.add(root);
a.addAll(q);
while(!a.isEmpty()){
//如何分层???设置两个队列
double i = 0; //用于记录当前层数的个数
double sum = 0;
Queue<TreeNode> t = new LinkedList<>();
a = t;
while(!q.isEmpty()){
TreeNode temp = q.poll();
sum += temp.val;
i++;
if(temp.left!=null){
a.add(temp.left);
}
if(temp.right!=null){
a.add(temp.right);
}
}
q = a;
en.add(sum/i);
}
return en;
}
}

代码二(类似)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
public List<Double> averageOfLevels(TreeNode root) {
List<Double> ret = new ArrayList<>();
if (root == null) return ret;
Queue<TreeNode> queue = new LinkedList<>();
queue.add(root);
while (!queue.isEmpty()) {
int cnt = queue.size();
double sum = 0;
for (int i = 0; i < cnt; i++) {
TreeNode node = queue.poll();
sum += node.val;
if (node.left != null) queue.add(node.left);
if (node.right != null) queue.add(node.right);
}
ret.add(sum / cnt);
}
return ret;
}

找树左下角的值

该算法主要还是使用两个循环来进行分层处理,找到最底下那一层,然后输出最后一层的第一个数据即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
class Solution {
public int findBottomLeftValue(TreeNode root) {
//利用上题思路,继续进行层次遍历,
if(root==null) return 0;
Queue<TreeNode> q = new LinkedList<>();
Queue<TreeNode> a = new LinkedList<>();
List<Integer> res = new ArrayList<>();
q.add(root);
a = q;
while(!a.isEmpty()){
Queue<TreeNode> t = new LinkedList<>();
a = t;
res.clear();
while(!q.isEmpty()){
TreeNode tmp = q.poll();
res.add(tmp.val);
if(tmp.left!=null){
a.offer(tmp.left);
}
if(tmp.right!=null){
a.offer(tmp.right);
}
}
q = a;
}
return res.get(0);
}
}

方法二(左右入队顺序一定不要反)

1
2
3
4
5
6
7
8
9
10
public int findBottomLeftValue(TreeNode root) {
Queue<TreeNode> queue = new LinkedList<>();
queue.add(root);
while (!queue.isEmpty()) {
root = queue.poll();
if (root.right != null) queue.add(root.right);
if (root.left != null) queue.add(root.left);
}
return root.val;
}

前中后序遍历

递归实现我在之前的博客数据结构-树的基础知识之中已经讲解过了,这里重点说一下非递归的遍历实现方法。

颜色标记法

该方法可用于各种遍历,是一种非递归算法。其核心思想如下:

  • 使用颜色标记节点的状态,新节点为白色,已访问的节点为灰色。
  • 如果遇到的节点为白色,则将其标记为灰色,然后将其右子节点、自身、左子节点依次入栈(前中后序顺序不同,注意调整)。
  • 如果遇到的节点为灰色,则将节点的值输出。

下面代码是中序遍历的实现方法:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
class Solution {
class ColorNode {
TreeNode node;
String color;

public ColorNode(TreeNode node,String color){
this.node = node;
this.color = color;
}
}
public List<Integer> inorderTraversal(TreeNode root) {
if(root == null) return new ArrayList<Integer>();

List<Integer> res = new ArrayList<>();
Stack<ColorNode> stack = new Stack<>();
stack.push(new ColorNode(root,"white"));

while(!stack.empty()){
ColorNode cn = stack.pop();

if(cn.color.equals("white")){
if(cn.node.right != null) stack.push(new ColorNode(cn.node.right,"white"));
stack.push(new ColorNode(cn.node,"gray"));
if(cn.node.left != null)stack.push(new ColorNode(cn.node.left,"white"));
}else{
res.add(cn.node.val);
}
}

return res;
}
}

迭代-前序遍历

前序遍历很简单,和上面的层次遍历差不多。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
public List<Integer> preorderTraversal(TreeNode root) {
List<Integer> res = new ArrayList<>();
Stack<TreeNode> s = new Stack<>();
s.push(root);
while(!s.isEmpty()){
TreeNode tmp = s.pop();
if(tmp==null) continue;
res.add(tmp.val);
if(tmp.right!=null) s.push(tmp.right); //!!!顺序很重要!!!
if(tmp.left!=null) s.push(tmp.left);
}
return res;
}
}

迭代-中序遍历

官方题解中介绍了三种方法来完成树的中序遍历,包括:

  • 递归
  • 借助栈的迭代方法
  • 莫里斯遍历

借助栈的迭代方法:中序遍历我们采取先遍历左子树、根节点、遍历右子树的规则来进行,显而易见,这很容易使用递归来解决,如果我们不用递归的话,可以考虑用循环迭代的方式来进行。对于中序遍历来说,我们仍然需要利用栈这一数据结构后进先出这一特性,然后根据遍历的实际顺序来进行调整。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public List<Integer> inorderTraversal(TreeNode root) {
List<Integer> res = new ArrayList<>();
if(root==null) return res;
Stack<TreeNode> s = new Stack<>();
TreeNode tmp = root;
while(tmp!=null||!s.isEmpty()){
while(tmp!=null){
s.push(tmp);
tmp = tmp.left;
}
tmp = s.pop();
res.add(tmp.val);
tmp = tmp.right;
}
return res;
}
}

刚刚使用了非递归,现在使用递归:

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
public void dfs(TreeNode root,List<Integer> res){
if(root==null) return;
dfs(root.left,res);
res.add(root.val);
dfs(root.right,res);
}
public List<Integer> inorderTraversal(TreeNode root) {
List<Integer> res = new ArrayList<>();
dfs(root,res);
return res;
}
}

莫里斯遍历

该遍历用到了线索二叉树,大家不明白的可自行百度。

迭代-后序遍历

前序遍历为 root -> left -> right,后序遍历为 left -> right -> root。可以修改前序遍历成为 root -> right -> left,那么这个顺序就和后序遍历正好相反。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public List<Integer> postorderTraversal(TreeNode root) {
List<Integer> res = new ArrayList<>();
if(root==null) return res;
Stack<TreeNode> s = new Stack<TreeNode>();
s.push(root);
while(!s.isEmpty()){
TreeNode tmp = s.pop();
res.add(tmp.val);
if(tmp.left!=null) s.push(tmp.left);
if(tmp.right!=null) s.push(tmp.right);
}
Collections.reverse(res);
return res;
}
}

BST相关

其定义请点击这里进行查看,下面给出相应的题目操作。

修建二叉搜索树

题目请自行点击查看,这里给出递归思路:

  • 如果当前 root 正好在范围之内,那么把问题递归到它的左结点和右结点。
  • 如果当前 root 不在范围内,比 L 小,那么 它和它的左子树 可以被抛弃了。
  • 如果当前 root 不在范围内,比 R 大,那么 它和它的右子树 可以被抛弃了。
1
2
3
4
5
6
7
8
9
10
class Solution {
public TreeNode trimBST(TreeNode root, int L, int R) {
if(root==null) return null;
if(root.val<L) return trimBST(root.right,L,R);
if(root.val>R) return trimBST(root.left,L,R);
root.left = trimBST(root.left,L,R);
root.right = trimBST(root.right,L,R);
return root;
}
}

把二叉搜索树转换为累加树

利用二叉搜索树独特的性质,我们利用中序遍历(RDL)的方式,将全部节点读出。显而易见,该遍历结果将是从大到小的顺序,那该题中就是13,5,2。依题意,累加树中每个节点的值是原来的节点值加上所有大于它的节点值之和。所以,我们就是从前往后加值:13 = 13 13+5=18 13+5+2=20

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public void inorder(TreeNode root,List<Integer> s){
if(root==null) return;
inorder(root.right,s); //先右后左
s.add(root.val);
for(int i = 0;i<s.size()-1;i++){
root.val += s.get(i);
}
inorder(root.left,s);
}
public TreeNode convertBST(TreeNode root) {
List<Integer> s = new ArrayList<>();
inorder(root,s);
return root;
}
}

代码优化,本来考虑使用List容器的,后来考虑发现完全没有必要,还因此这增加了运行时间,所以,修改后为

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
private int sum = 0;
public void inorder(TreeNode root){
if(root==null) return;
inorder(root.right);
sum+=root.val;
root.val = sum;
inorder(root.left);
}
public TreeNode convertBST(TreeNode root) {
inorder(root);
return root;
}
}

二叉搜索树的最近公共祖先

看到该题我的初步想法为:寻找并存储从根节点开始到q p结点的路径,等全部完成之后对比两路径的相似度,最后一个相似的就是两个人的最近公共祖先。顺带实现了一下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
public TreeNode searchNode(TreeNode root,TreeNode node,List<TreeNode> tmp){
//因为题目限定一定能找得到
tmp.add(root);
if(root.val==node.val) return root;
else if(root.val>node.val) return searchNode(root.left,node,tmp);
else return searchNode(root.right,node,tmp);
}
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
//打算从根节点来寻找唯一的一条路径
//然后对比其相同的那个节点
List<TreeNode> a = new ArrayList<>();
searchNode(root,p,a);
List<TreeNode> b = new ArrayList<>();
searchNode(root,q,b);
TreeNode t = new TreeNode(0);
for(int i = 0;i<Math.min(a.size(),b.size());i++){
if(a.get(i).val==b.get(i).val){
t = a.get(i);
}
}
return t;
}
}

代码二:同时搜索,分叉的时候就是最近公共祖先了。但是因为是使用递归来进行,所以空间耗用比较大。

1
2
3
4
5
6
7
8
9
10
class Solution {
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {

if(p.val<root.val && q.val<root.val)
return lowestCommonAncestor(root.left,p,q);
if(p.val>root.val && q.val>root.val)
return lowestCommonAncestor(root.right,p,q);
return root;
}
}

代码三:迭代方式,下面给出代码。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
while(root!=null){
if(p.val > root.val && q.val > root.val){
root = root.right;
}
else if(p.val < root.val && q.val < root.val){
root = root.left;
}
else break;
}
return root;
}
}

二叉树的最近公共祖先

这题与上一题的区别在于,该树没有了搜索二叉树的限制,变成了更普通的二叉树。但是这样思路也不变,首先在二叉树中搜索给定的节点 p 和 q,然后找到它们的最近共同祖先。我们可以使用普通的树遍历来搜索这两个节点。一旦我们达到所需的节点 p 和 q,我们就可以回溯并找到最近的共同祖先。

1
2
3
4
5
6
7
8
class Solution {
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
if(root==null||root==q||root==p) return root;
TreeNode left = lowestCommonAncestor(root.left, p, q);
TreeNode right = lowestCommonAncestor(root.right, p, q);
return left == null ? right : right == null ? left : root;
}
}

未完待续……

等我学习完图的相关数据结构,再回来继续更新……

您的每一份支持将鼓励我继续创作!
-------------本文结束感谢您的阅读-------------