当前位置：首页 > news >正文

数据结构（Java）：力扣牛客二叉树面试OJ题（一）

news 来源：原创 2024/9/19 1:56:21

👉 目录 👈

1、题一：检查两棵树是否相同

1.1 思路分析

1.2 代码

2、题二：另一棵树的子树

2.1 思路分析

2.2 代码

3、题三：翻转二叉树

3.1 思路分析

3.2 代码

4、题四：判断树是否对称

4.1 思路分析

4.2 代码

5、题五：判断是否为平衡二叉树

5.1 思路分析

5.1.1 平衡二叉树概念

5.1.2 思路一 O(n^2)

5.1.3 思路一代码

5.1.4 思路二：改善为O(n)【字节跳动面试题】

5.1.5 思路二代码

6、题六：将二叉搜索树转化为有序的双向链表

6.1 二叉搜索树的性质

6.2 思路分析

6.3 代码

7、题七：二叉树的遍历和构建

7.1 思路分析

7.2 代码

1、题一：检查两棵树是否相同

. - 力扣（LeetCode）

1.1 思路分析

两棵树相同，需要注意以下几点：

两棵树结构相同，若结构不相同，那两棵树必然是不相同的
在结构相同的前提下，还需满足节点值相同
若结构和节点值都相同，那么两棵树相同

额外注意的是：若两棵树为空，那么也是相同的。

我们可以按照子问题遍历的思想，当左子树和右子树中全部节点同时满足以上条件，说明两棵树相等。

1.2 代码

时间复杂度：O（min（m,n））

class Solution {public boolean isSameTree(TreeNode p, TreeNode q) {//如果两棵树都为空，那么两棵树相同if(p == null && q == null) {return true;}//如果两棵树的结构不同，那这两棵树必然不同if(p != null && q == null || p == null && q != null) {return false;}//走到这里，说明两棵树的结构相同且不为空，那判断他们的节点值即可//若节点值不相同，则说明两棵树不相同，返回falseif(p.val != q.val) {return false;}//递归遍历//左右两棵子树必须同时满足条件 //才能说明两棵树才相同return isSameTree(p.left,q.left) &&isSameTree(p.right,q.right);}
}

2、题二：另一棵树的子树

. - 力扣（LeetCode）

2.1 思路分析

一棵树的子树需要满足：

这棵子树包括主树的某个节点，和这个节点的所有后代节点
这棵树自身，也可看做自己的子树

了解子树概念后，我们可以按照以下思路解决问题：

判断子树根节点subRoot和主树根节点root是否相同
若相同，则调用检查两棵树是否相同的方法（题一），若相同，则为子树
若不相同，继续遍历，判断子树是否和root的左子树相同
若不相同，继续遍历，判断子树是否和root的右子树相同
递归解决问题

2.2 代码

时间复杂度：O(m*n)

因为最坏的情况下：

每个节点和子树值相同，但判断树是否相同时，总是最后一个节点不相同

 /**时间复杂度为：O(m*n)因为最坏的情况下：每个节点和子树值相同，但判断树是否相同时，总是最后一个节点不相同
*/
class Solution {public boolean isSubtree(TreeNode root, TreeNode subRoot) {//如果递归到空，说明没有找到子树，返回falseif(root == null) {return false;}//判断当前节点的整颗树和子树是否相同即可if(isSameTree(root,subRoot)) {return true;}//如果递归遇见了子树 则一路返回trueif(isSubtree(root.left,subRoot)) return true;if(isSubtree(root.right,subRoot)) return true;//本次递归没有找见子树 返回falsereturn false;}public boolean isSameTree(TreeNode p, TreeNode q) {// 1.先判断结构是否是一样的if (p != null && q == null || p == null && q != null) {return false;}// 上述if语句 如果没有执行，意味着两个引用 同时为空 或者同时不为空if (p == null && q == null) {return true;}// 都不为空 判断值是否一样if (p.val != q.val) {return false;}// 都不为空且值一样return isSameTree(p.left, q.left) && isSameTree(p.right, q.right);}
}

3、题三：翻转二叉树

. - 力扣（LeetCode）

3.1 思路分析

这道题的思路很简单，就是：将每个节点的左右子树进行交换。

我们可以以前序遍历思想遍历所有节点，在访问当前树的根节点时将其左右子树进行交换。

3.2 代码

根据解题思想，很清晰的分析出时间复杂度为：O（n）

class Solution {public TreeNode invertTree(TreeNode root) {if(root == null) {return null;}//交换左右子树swapNode(root);invertTree(root.left);invertTree(root.right);return root;}public void swapNode(TreeNode root) {TreeNode tmp = root.left;root.left = root.right;root.right = tmp;}
}

4、题四：判断树是否对称

. - 力扣（LeetCode）

4.1 思路分析

要判断这颗树是对称的，

就要判断，根节点的左子树和右子树是对称的
要判断根节点的左子树和右子树是对称的，需要左右子树的结构相同；在结构相同前提下，节点的值要相同
如果结构相同了，值也相同了，那么要递归去判断：左子树的左树和右子树的右树是否轴对称（是否结构相同、值相同）；以及左子树的右树和右子树的左树是否轴对称（是否结构相同、值相同）。（均满足）
我们只能递归来一个节点一个节点的去遍历，去判断，去比较

4.2 代码

class Solution {public boolean isSymmetric(TreeNode root) {if(root == null) {return true;}return isSymmetricChild(root.left,root.right);}public boolean isSymmetricChild(TreeNode leftTree,TreeNode rightTree) {//空树对称if(leftTree == null && rightTree == null) {return true;}//结构不相同 必定不对称if(leftTree != null && rightTree == null || leftTree == null && rightTree != null) {return false;}//节点值不相同 必定不对称if(leftTree.val != rightTree.val) {return false;}//左子树的左树和右子树的右树 //左子树的右树和右子树的左树//都要对称return isSymmetricChild(leftTree.left,rightTree.right) && isSymmetricChild(leftTree.right,rightTree.left);}
}

5、题五：判断是否为平衡二叉树

. - 力扣（LeetCode）

5.1 思路分析

5.1.1 平衡二叉树概念

如果一棵树是平衡二叉树，那么满足：

树中所有节点的左右子树高度差<=1
也就是说，每一棵子树都是平衡二叉树

根据平衡二叉树的概念，我们有以下两种思路解决问题。

5.1.2 思路一 O(n^2)

递归遍历所有节点，求出每个节点的左右子树高度差，若出现>=2的情况，立即返回false
当前节点的左树上的节点和右树上的节点全部满足高度差<=1 时，说明为平衡二叉树
该思路时间复杂度为O（n^2），求根节点高度的方法时间复杂度本来就为O（n），而要求得所有节点的高度，时间复杂度就为O（n^2）

5.1.3 思路一代码

class Solution {public boolean isBalanced(TreeNode root) {//空树 平衡if(root == null) {return true;}//当前节点左子树高度int h1 = getHeight(root.left);//当前节点右子树高度int h2 = getHeight(root.right);int h = Math.abs(h1-h2);//高度差//不平衡if(h >= 2) return false;//左子树和右子树同时平衡 说明整棵树平衡return isBalanced(root.left) &&isBalanced(root.right);}public int getHeight(TreeNode root) {if (root == null) {return 0;}int leftHeight = getHeight(root.left);int rightHeight = getHeight(root.right);//树的高度为 左子树高度和右子树高度的最大值+节点自身的1个高度return leftHeight > rightHeight? leftHeight + 1: rightHeight + 1;}
}

5.1.4 思路二：改善为O(n)【字节跳动面试题】

思路一虽然能解决问题，但时间复杂度达到了O(n^2)，并且产生了很多次重复的计算,例如：圈中节点的高度，在计算它祖先的高度时就被计算了多次，产生了很多重复的计算。

如果要将时间复杂度改善为O(n)，该如何完成呢？

O(n)思路分析：

我们可以只求根节点的高度
在求节点高度时，我们使用递归遍历思想，返回的是左右子树高度的最大值+1（左右子树最大高度+节点自身1个高度）
而我们可以将求高度的方法进行改善，在递归过程中，一旦发现左右子树高度差绝对值>=2时（说明不平衡），立即返回负数（标记，其他标记也可）；如果高度差绝对值<=1时（说明平衡），返回正常的高度值即可。如若发现返回的是负数，立即一路返回负数。
最终判断方法的返回值即可，若为负数，则说明该树不平衡；若为正数（高度值），说明该树平衡。

5.1.5 思路二代码

class Solution {/**时间复杂度：O（n）*/public boolean isBalanced(TreeNode root) {if(root == null) {return true;}//负数说明该树不平衡return getHeight(root) > 0;}public int getHeight(TreeNode root) {if (root == null) {return 0;}int leftHeight = getHeight(root.left);//如若发现返回的是负数，则说明该树一定不平衡，一路返回负数if(leftHeight < 0) {return -1;}//如若发现返回的是负数，则说明该树一定不平衡，一路返回负数int rightHeight = getHeight(root.right);if(rightHeight < 0) {return -1;}//如果绝对值<=1 说明当前树平衡，返回高度值if(Math.abs(leftHeight - rightHeight) <= 1) {return Math.max(leftHeight , rightHeight) + 1;}else {//否则返回负数return -1;}}
}

6、题六：将二叉搜索树转化为有序的双向链表

二叉搜索树与双向链表_牛客题霸_牛客网

6.1 二叉搜索树的性质

二叉搜索树，又称二叉排序树、二叉查找树，具有以下性质：

若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值；
若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值；
二叉搜索树可以为空树
以中序遍历来遍历一棵二叉搜索树，那么得到的序列就是一个有序的升序序列。

6.2 思路分析

以中序遍历递归这棵二叉搜索树，将得到的根节点依次连接（修改其左右指针），得到的就是排好序的双向链表。

借助中序遍历思想递归，遍历各个节点，修改指向
将每个节点的left域当做双向链表中的prev域，将right域当做next域
借助一个成员变量prev，存储上一个节点的地址，完成各节点指向的修改和连接

6.3 代码

时间复杂度：O（n）

public class Solution {//定义一个成员变量 存储上一个节点的地址TreeNode prev;//初始值为nullpublic void ConvertNode(TreeNode pRootOfTree) {if(pRootOfTree == null) return;//中序遍历思想递归ConvertNode(pRootOfTree.left);//修改前驱，将当前节点的left域更改为前一个节点的地址pRootOfTree.left = prev;if (prev != null) {//当prev不为空时，修改后继//将其right域修改为当前节点的地址（prev本就是当前节点的前驱）prev.right = pRootOfTree;}//更新prevprev = pRootOfTree;ConvertNode(pRootOfTree.right);}public TreeNode Convert(TreeNode pRootOfTree) {if (pRootOfTree == null) {return null;}ConvertNode(pRootOfTree);TreeNode head = pRootOfTree;//找头结点//转换成双向链表后，链表的头结点就在pRootOfTree的左边//头结点的left（前驱）为nullwhile(head.left != null) {head = head.left;}return head;}
}

7、题七：二叉树的遍历和构建

二叉树遍历_牛客题霸_牛客网

7.1 思路分析

我们知道，如果仅仅根据一个遍历方式的结果是无法构建出一棵二叉树的，必须有两个遍历方式且必须包含中序遍历。

而这道题是不同的，因为题目给出的遍历结果包含了空树，所以仅仅利用一个遍历方式我们就可以构建出二叉树。

只要构建出这棵二叉树，我们再使用中序遍历递归打印节点值就可以了。

难点在，如何使用代码根据前序遍历来构建二叉树？

思路如下：

题目仅仅给出了main方法，意味着我们要自己创建节点，创建的节点类要满足树中节点的要求，包含val域（char类型）、left域、right域，同时要给出构造方法
创建二叉树，肯定是要遍历前序遍历结果的字符串（这里以静态i成员遍历字符串）
给出的是前序遍历结果，所以要以前序遍历的思想递归来创建树
如果遍历到的字符不是'#'，说明不是空树，实例出该值的节点，i++（此时仅仅实例节点，各节点间并没有连接）
创建左子树，创建右子树
如果遇到的字符是'#'，说明遇到是空树，i++，返回空节点（递归回退），上一个节点的left或者right接收
如果节点的左子树或者右子树创建完成，递归回退，上一个节点的left或者right接收
如果节点的左子树和右子树都创建完成（本次递归函数结束），递归回退，上一个节点的left或者right接收
也就是说，我们在递归回退的过程中，完成节点之间的连接
最后一步，以中序遍历形式来访问根节点并打印

注意：这里因为题目条件限制，只能使用静态成员i来遍历字符串。但是对于我们实际的应用，不建议使用静态成员，因为当创建多个对象时，他们都会使用并改变i的值，而创建二叉树时，必须从0下标处遍历字符串！！！

7.2 代码

import java.util.Scanner;//节点
class TreeNode {TreeNode left;TreeNode right;char val;public TreeNode(char val) {this.val = val;}
}
// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {public static void main(String[] args) {Scanner in = new Scanner(System.in);// 注意 hasNext 和 hasNextLine 的区别while (in.hasNextLine()) { // 注意 while 处理多个 case//防止有多组测试用例，每次使用时i要置0Main.i = 0;String str = in.nextLine();TreeNode root = creatTree(str);InOrder(root);}}public static int i;public static TreeNode creatTree(String str) {TreeNode node = null;if (str.charAt(i) != '#') {//不是空树，就实例化该值的节点node = new TreeNode(str.charAt(i));i++;//在递归回退的过程中，完成节点之间的连接node.left = creatTree(str);node.right = creatTree(str);} else {//是空树，i++i++;}return node;}//中序遍历，打印根节点public static void InOrder(TreeNode root) {if (root == null) {return;}InOrder(root.left);System.out.print(root.val + " ");InOrder(root.right);}
}