作者：学Java的冬瓜
博客主页：☀冬瓜的主页🌙
专栏：【Java 数据结构】
分享：宇宙的最可理解之处在于它是不可理解的，宇宙的最不可理解之处在于它是可理解的。——《乡村教师》
主要内容： 二叉树的各类OJ习题，面试题
刷题网站：【牛客网】 【LeetCode官网】
文章目录
*
– 题一：判断二叉树是否完全相同
–
+ 0、链接：
+ 1、思路：
+ 2、代码：
+
* 法一：使用 if-else
* 法二：使用 if 排除
+ 3、时间复杂度：
– 题二：判断另一棵树的子树
–
+ 0、链接：
+ 1、思路：
+ 2、代码：
+
* 法一：使用 if-else
* 法二：使用 if 排除
+ 3、时间复杂度：
– 题三：翻转二叉树
–
+ 0、链接：
+ 1、思路：
+ 2、代码：
+ 3、时间复杂度：
– 题四：判断平衡二叉树
–
+ 0、链接：
+ 1、思路：
+ 2、代码+复杂度：
+
* 法一：使用双重递归
* 法二：只使用深度递归同时判断平衡
– 题五：二叉树的层序遍历(非递归)
–
+ 0、链接：
+ 1、思路：
+ 2、代码：
– 题六：判断完全二叉树
–
+ 1、思路：
+ 2、代码：
– 题七：二叉树创建和遍历
–
+ 0、链接：
+ 1、代码：
+
* 分析法一：
* 法一：利用全局变量i
* 分析法二：
* 法二：使用队列解决法一带来的多线程问题
– 题八：二叉树前序遍历
–
+ 0.链接
+ 1.代码
+
* 法一：递归
* 法二：非递归
– 题九：二叉树中序遍历
–
+ 0、链接
+ 1、代码
– 题十：二叉树后序遍历
–
+ 0、链接
+ 1、代码
– 题十一：二叉树的最近公共祖先
–
+ 0、链接：
+ 1、代码：
+
* 法一：利用双栈
*
– 非递归
– 利用递归(路径函数)
* 法二：分情况讨论
– 题十二：二叉搜索树与双向链表
–
+ 0、链接：
+ 1、思路：
+ 2、代码：利用prev引用
– 题十三：从前序和中序遍历序列构造二叉树
–
+ 0、链接：
+ 1、思路：
+ 2、代码：
– 题十四：从中序和后序遍历序列构造二叉树
–
+ 0、链接：
+ 1、思路：
+ 2、代码：
– 题十五：根据二叉树创建字符串
–
+ 0、链接：
+ 1、思路：
+ 2、代码：
; 题一：判断二叉树是否完全相同
0、链接：
1、思路：
分析：分为p，q两棵树都空，一棵树空，另一棵树不空。两棵树都不空三种情况。再详细分析
2、代码：
法一：使用 if-else
class Solution {
public boolean isSameTree(TreeNode p, TreeNode q) {
if(p == null && q == null){
return true;
}
else if((p == null && q != null) || (p != null && q == null)){
return false;
}
else{
if(p.val != q.val){
return false;
}
return isSameTree(p.left,q.left) && isSameTree(p.right,q.right);
}
}
}
法二：使用 if 排除
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;
}
if(p.val != q.val){
return false;
}
return isSameTree(p.left,q.left) && isSameTree(p.right,q.right);
}
3、时间复杂度：
O(min(m,n))
题二：判断另一棵树的子树
0、链接：
1、思路：
分析：
1> 判断两棵树是否相等，相等就可看做subRoot为root子树成立
2> 不等时进入递归循环查找是否符合subRoot是roor的左子树或者右子树。
2、代码：
法一：使用 if-else
class Solution {
public boolean isSubtree(TreeNode root, TreeNode subRoot) {
if(isSameTree(root,subRoot)){
return true;
}
else if(root == null){
return false;
}
else{
return isSubtree(root.left,subRoot) || isSubtree(root.right,subRoot);
}
}
public static boolean isSameTree(TreeNode p, TreeNode q) {
if(p == null && q == null){
return true;
}
else if((p == null && q != null) || (p != null && q == null)){
return false;
}
else{
if(p.val != q.val){
return false;
}
return isSameTree(p.left,q.left) && isSameTree(p.right,q.right);
}
}
}
法二：使用 if 排除
class Solution {
public boolean isSubtree(TreeNode root, TreeNode subRoot) {
if(root == null){
return false;
}
if(isSameTree(root,subRoot)){
return true;
}
if(isSubtree(root.left,subRoot)){
return true;
}
if(isSubtree(root.right,subRoot)){
return true;
}
return false;
}
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;
}
if(p.val != q.val){
return false;
}
return isSameTree(p.left,q.left) && isSameTree(p.right,q.right);
}
3、时间复杂度：
O(r*s)
题三：翻转二叉树
0、链接：
1、思路：
分析：从视觉上看是反转了二叉树每一层的数据。其实就是交换了每一个结点的左右子树
2、代码：
class Solution {
public TreeNode invertTree(TreeNode root) {
if(root == null){
return null;
}
TreeNode tmp = root.left;
root.left = root.right;
root.right = tmp;
invertTree(root.left);
invertTree(root.right);
return root;
}
}
3、时间复杂度：
O(N)
题四：判断平衡二叉树
0、链接：
1、思路：
分析：
要求这棵树是平衡二叉树，那么必须是这棵树的左右子树都为平衡二叉树。
当root=null时，要么是根节点为空，返回true；要么是叶子节点的子节点为空，说明这个空的父节点们满足isBalance条件，所以也返回true。
2、代码+复杂度：
法一：使用双重递归
class Solution {
public boolean isBalanced(TreeNode root) {
if(root == null){
return true;
}
int leftDepth = treeDepth(root.left);
int rightDepth = treeDepth(root.right);
int sub = leftDepth - rightDepth;
return sub >= -1 && sub 1 && isBalanced(root.left) && isBalanced(root.right);
}
public int treeDepth(TreeNode root){
if(root == null){
return 0;
}
int leftDepth = treeDepth(root.left);
int rightDepth = treeDepth(root.right);
return leftDepth > rightDepth ? leftDepth+1 : rightDepth+1;
}
}
法二：只使用深度递归同时判断平衡
class Solution {
public boolean isBalanced(TreeNode root) {
if(root == null){
return true;
}
return treeDepth(root) >= 0;
}
public int treeDepth(TreeNode root){
if(root == null){
return 0;
}
int leftDepth = treeDepth(root.left);
int rightDepth = treeDepth(root.right);
if(leftDepth >=0 && rightDepth >= 0 && Math.abs(leftDepth - rightDepth) < 2){
return leftDepth > rightDepth ? leftDepth+1 : rightDepth+1;
}else{
return -5;
}
}
}
题五：二叉树的层序遍历(非递归)
0、链接：
简单的中序遍历，再打印可以参考这篇C语言博客：
【二叉树基础习题】
1、思路：
说明：
1>先创建一个队列，先把树的根节点入队列
2>然后队列不空就把队头元素取出，再把这个元素的左右子树的非空的根节点入队列
3>最后队列为空时结束
2、代码：
class Solution {
public List<List<Integer>> levelOrder(TreeNode root) {
List<List<Integer>> lists = new ArrayList<>();
if (root == null){
return lists;
}
Queue<TreeNode> queue = new LinkedList<>();
queue.offer(root);
while (!queue.isEmpty()){
int cnt = queue.size();
List<Integer> list = new ArrayList<>();
while(cnt > 0){
TreeNode out = queue.poll();
if(out != null){
list.add(out.val);
}
if(out.left != null){
queue.offer(out.left);
}
if(out.right != null){
queue.offer(out.right);
}
cnt--;
}
lists.add(list);
}
return lists;
}
}
题六：判断完全二叉树
1、思路：
说明：这道题不是OJ题，方法和层序遍历非递归的方法非常相似。
思路：
1>按照非递归层序遍历的方式，把所以节点入队列包括null。
2>当遇到null时，退出循环，再判断此时队列中是否有非null的元素，如有非null元素，则不是完全二叉树，返回false。
3>若不断出队，最后队列为空了，也还没返回false，则是完全二叉树，返回true。
注意：在C语言中NULL不能入队，所以这个方法不能用C语言实现。
2、代码：
public static boolean isCompleteTree(TreeNode root){
if (root == null){
return false;
}
Queue<TreeNode> qu = new LinkedList<>();
qu.offer(root);
while (!qu.isEmpty()){
TreeNode cur = qu.poll();
if (cur != null){
qu.offer(cur.left);
qu.offer(cur.right);
}else{
break;
}
}
while(!qu.isEmpty()){
if(qu.poll() != null){
return false;
}
}
return true;
}
题七：二叉树创建和遍历
0、链接：
1、代码：
分析法一：
方法一：
定义全局变量，来控制当前的字符位置，但是在多线程中，容易错误，因为线程是不断在切换的。不推荐使用。
法一：利用全局变量i
import java.util.*;
public class Main {
static class TNode{
char val;
TNode left;
TNode right;
public TNode(char value){
this.val = value;
}
}
static int i = 0;
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
String s = in.nextLine();
TNode root = createTree(s);
inOrder(root);
}
private static TNode createTree(String s){
char ch = s.charAt(i++);
if(ch == '#'){
return null;
}
TNode node = new TNode(ch);
node.left = createTree(s);
node.right = createTree(s);
return node;
}
private static void inOrder(TNode root){
if(root == null){
return;
}
inOrder(root.left);
System.out.print(root.val + " ");
inOrder(root.right);
}
}
分析法二：
方法二：
在main方法中，把字符串放入队列，由队列进行操作。相当于用队列代替了用i遍历字符串的任务。因为队列遍历remove后，不会因为递归而回到上一个字符(如果用局部变量i则会出这个问题)。但是效率比法一低，看情况取舍。
注意：
若需要该题C语言版的，这篇博客步骤讲的更详细一点，可以点以下链接：【牛客.二叉树遍历】-C语言
法二：使用队列解决法一带来的多线程问题
import java.util.*;
public class Main {
static class TNode{
char val;
TNode left;
TNode right;
public TNode(char value){
this.val = value;
}
}
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
String s = in.nextLine();
Queue<Character> queue = new LinkedList<>();
for(char ch : s.toCharArray()){
queue.offer(ch);
}
TNode root = createTree(queue);
inOrder(root);
}
private static TNode createTree(Queue<Character> queue){
char ch = queue.remove();
if(ch == '#'){
return null;
}
TNode node = new TNode(ch);
node.left = createTree(queue);
node.right = createTree(queue);
return node;
}
private static void inOrder(TNode root){
if(root == null){
return;
}
inOrder(root.left);
System.out.print(root.val + " ");
inOrder(root.right);
}
}
题八：二叉树前序遍历
注解：在之前我写过一篇关于二叉树的各种遍历问题的博客，不太懂的小伙伴可以去看看这篇博客
链接：【二叉树的各种遍历问题】
0.链接
1.代码
法一：递归
class Solution {
public List<Integer> preorderTraversal(TreeNode root) {
List<Integer> list = new ArrayList<>();
preOrder(root,list);
return list;
}
private static TreeNode preOrder(TreeNode root,List<Integer> list){
if(root == null){
return null;
}
list.add(root.val);
preOrder(root.left,list);
preOrder(root.right,list);
return root;
}
}
法二：非递归
class Solution {
public List<Integer> preorderTraversal(TreeNode root) {
TreeNode cur = root;
List<Integer> list = new ArrayList<>();
Stack<TreeNode> stack = new Stack<>();
while(cur!=null || !stack.isEmpty()){
if(cur != null){
stack.push(cur);
list.add(cur.val);
cur = cur.left;
}else{
cur = stack.pop();
cur = cur.right;
}
}
return list;
}
}
题九：二叉树中序遍历
说明：中序遍历的递归算法和前序遍历算法差不多，这里就不再做过多赘述，有疑问，则看题七中的链接。
0、链接
1、代码
class Solution {
public List<Integer> inorderTraversal(TreeNode root) {
TreeNode cur = root;
Stack<TreeNode> stack = new Stack<>();
List<Integer> list = new ArrayList<>();
while(cur!=null || !stack.isEmpty()){
if(cur != null){
stack.push(cur);
cur = cur.left;
}else{
cur = stack.pop();
list.add(cur.val);
cur = cur.right;
}
}
return list;
}
}
题十：二叉树后序遍历
0、链接
1、代码
class Solution {
public List<Integer> postorderTraversal(TreeNode root) {
TreeNode cur = root;
TreeNode prev = null;
Stack<TreeNode> stack = new Stack<>();
List<Integer> list = new ArrayList<>();
while(cur!=null || !stack.isEmpty()){
if(cur!=null){
stack.push(cur);
cur = cur.left;
}else{
TreeNode top = stack.peek();
if(top.right == null || top.right==prev){
cur = stack.pop();
list.add(cur.val);
prev = cur;
cur = null;
}else{
cur = top.right;
}
}
}
return list;
}
}
题十一：二叉树的最近公共祖先
0、链接：
1、代码：
法一：利用双栈
原理：
从祖先节点到p或者q节点的深度是确定的，我们用两个栈来分别储存最近祖先节点到p和q的所有节点。
方法：
1> 用pstack储存根节点到p节点的路径，pstack的元素个数就是p的深度。 用qstack储存根节点到q节点的路径，qstack的元素个数就是q的深度。
2> 把pstack和qstack中元素个数大的出栈，变成和小的一样的个数，这一步的目的是让搜索来到同一高度。
3> pstack和qstack出栈，然后比较元素是否相等，如果相等就是最近公共祖先，返回该节点；如果都空栈了还不相等就返回null。
4> 要使用后序遍历非递归中栈的使用方法，才能把节点按照p或者q的路径存进栈中，然后遇到p或者要到q时，break跳出循环。
非递归
class Solution {
public static TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
if (root == null) {
return null;
}
Stack<TreeNode> ps = new Stack<>();
TreeNode pre1 = null;
TreeNode cur1 = root;
Stack<TreeNode> qs = new Stack<>();
TreeNode pre2 = null;
TreeNode cur2 = root;
while(cur1 != null || !ps.isEmpty()){
if(cur1 == p){
ps.push(cur1);
break;
}
if(cur1 != null){
ps.push(cur1);
cur1 = cur1.left;
}else{
TreeNode top = ps.peek();
if(top.right == null || top.right==pre1){
cur1 = ps.pop();
pre1 = cur1;
cur1 = null;
}else{
cur1 = top.right;
}
}
}
while(cur2 != null || !qs.isEmpty()){
if(cur2 == q){
qs.push(cur2);
break;
}
if(cur2 != null){
qs.push(cur2);
cur2 = cur2.left;
}else{
TreeNode top = qs.peek();
if(top.right == null || top.right==pre2){
cur2 = qs.pop();
pre2 = cur2;
cur2 = null;
}else{
cur2 = top.right;
}
}
}
int psize = ps.size();
int qsize = qs.size();
if(psize > qsize){
int size = psize - qsize;
while(size>0){
ps.pop();
size--;
}
}else{
int size = qsize - psize;
while(size>0){
qs.pop();
size--;
}
}
while (!ps.isEmpty()){
TreeNode ptnode = ps.pop();
TreeNode qtnode = qs.pop();
if(ptnode == qtnode){
return ptnode;
}
}
return null;
}
}
利用递归(路径函数)
class Solution {
public static TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
if (root == null) {
return null;
}
Stack<TreeNode> ps = new Stack<>();
getPath(root,p,ps);
Stack<TreeNode> qs = new Stack<>();
getPath(root,q,qs);
int psize = ps.size();
int qsize = qs.size();
if(psize > qsize){
int size = psize - qsize;
while(size>0){
ps.pop();
size--;
}
}else{
int size = qsize - psize;
while(size>0){
qs.pop();
size--;
}
}
while (!ps.isEmpty()){
TreeNode ptnode = ps.pop();
TreeNode qtnode = qs.pop();
if(ptnode == qtnode){
return ptnode;
}
}
return null;
}
private static boolean getPath(TreeNode root,TreeNode node, Stack<TreeNode> stack){
if(root == null || node == null){
return false;
}
stack.push(root);
if(root == node){
return true;
}
boolean left = getPath(root.left,node,stack);
if(left == true){
return true;
}
boolean right = getPath(root.right,node,stack);
if(right == true){
return true;
}
stack.pop();
return false;
}
}
法二：分情况讨论
分析：
可以大致分为，三种情况。
1> p和q有一个是根节点
2> p和q在根节点的两侧
3> p和q在根节点的一侧
方法：
在递归里，我只需要关心在当前节点的子树当中找没找到p或者q
如果p和q都在根节点的左边，需要两个节点都找到，才能返回公共祖先。
如果p和q在根节点的左右两侧，那就根节点是公共祖先
如果p和q都在根节点右侧，那先找到的那个节点就是公共祖先。
class Solution {
public static TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
if(root == null || p == null || q == null){
return null;
}
if(root == p || root == q){
return root;
}
TreeNode leftNode = lowestCommonAncestor(root.left,p,q);
TreeNode rightNode = lowestCommonAncestor(root.right,p,q);
if(leftNode != null && rightNode != null){
return root;
}
else if (leftNode != null) {
return leftNode;
} else if (rightNode != null) {
return rightNode;
}
else{
return null;
}
}
}
题十二：二叉搜索树与双向链表
0、链接：
1、思路：
说明：
1> 根据一个convertChild函数，加上prev属性引用(类似于指针传址)，去中序递归实现前驱和后继的改变。
2> 要注意最后的双向链表是中序遍历第一个节点left(前驱)为null（在代码上可以表现出来），中序遍历最后一个节点right(后继)为null，代码上体现不出来，但是这个节点的right本身在树中就是null。
3> 返回值是中序遍历的第一个节点，即节点的left为null的就是返回节点。
2、代码：利用prev引用
public class Solution {
public TreeNode Convert(TreeNode pRootOfTree) {
if(pRootOfTree == null){
return null;
}
convertChild(pRootOfTree);
TreeNode head = pRootOfTree;
while(head.left != null){
head = head.left;
}
return head;
}
private TreeNode prev = null;
private void convertChild(TreeNode pcur){
if(pcur == null){
return ;
}
convertChild(pcur.left);
pcur.left = prev;
if(prev != null){
prev.right = pcur;
}
prev = pcur;
convertChild(pcur.right);
}
}
题十三：从前序和中序遍历序列构造二叉树
0、链接：
1、思路：
说明：
1> 根据前序和中序构造二叉树，首先要确定的是前序依次从左往右的元素就是根节点，然后在中序中找到根节点位置，从这个位置左右拆分。
2> 因为每一段区间都是相同的操作，所以用递归实现。
3> 因为前序遍历是，根左右。所以我们根据前序和中序创建二叉树也是按照根左右来的，因为需要根据根的顺序创建二叉树。
2、代码：
class Solution {
public TreeNode buildTree(int[] preorder, int[] inorder) {
return buildTreeChild(preorder,inorder,0,inorder.length-1);
}
int preindex = 0;
private TreeNode buildTreeChild(int[] preorder,int[] inorder,int begindex,int Endindex){
if(begindex > Endindex){
return null;
}
TreeNode root = new TreeNode(preorder[preindex]);
int rootindex_inorder = findIndex(preorder,inorder);
preindex++;
root.left = buildTreeChild(preorder,inorder,begindex,rootindex_inorder-1);
root.right = buildTreeChild(preorder,inorder,rootindex_inorder+1,Endindex);
return root;
}
private int findIndex(int[] preorder,int[] inorder){
int i = 0;
while(i<inorder.length){
if(preorder[preindex] == inorder[i]){
return i;
}
i++;
}
return -1;
}
}
题十四：从中序和后序遍历序列构造二叉树
0、链接：
1、思路：
说明：
1> 大部分思路和上一道题相同
2> 不同点就是这里根节点序列的后序遍历顺序是，左右根。但是我们判断时是把这个序列倒起来看的，从而顺序找出根节点，所以创建二叉树的顺序就是根右左。
2、代码：
class Solution {
int postIndex = 0;
public TreeNode buildTree(int[] inorder, int[] postorder) {
postIndex = postorder.length-1;
return buildTreeChild(inorder,postorder,0,inorder.length-1);
}
private TreeNode buildTreeChild(int[] inorder, int[] postorder, int begindex, int endindex){
if(begindex>endindex){
return null;
}
TreeNode root = new TreeNode(postorder[postIndex]);
int rootindex_inorder = findIndex(inorder,postorder);
postIndex--;
root.right = buildTreeChild(inorder,postorder,rootindex_inorder+1,endindex);
root.left = buildTreeChild(inorder,postorder,begindex,rootindex_inorder-1);
return root;
}
private int findIndex(int[] inorder, int[] postorder){
int i = 0;
while(i<inorder.length){
if(inorder[i] == postorder[postIndex]){
return i;
}
i++;
}
return -1;
}
}
题十五：根据二叉树创建字符串
0、链接：
1、思路：
说明：要把左右子树的递归，放在if-else逻辑里面。分以下几种情况：
判断左边加什么：
1> 左边不为null，加数值 然后进入左递归 再加 “(”
2> 左边为null，右边不为null，加 “()”
3> 左边为null，右边直接返回，不加东西。
判断右边加什么：
1> 右边不为空，加数值 然后进入右递归 再加 “(”
2> 右边为null，直接返回（因为在不为空时已经加上了 “)” )
2、代码：
class Solution {
public String tree2str(TreeNode root) {
StringBuilder sb = new StringBuilder();
treeToStr(root,sb);
return sb.toString();
}
private void treeToStr(TreeNode root, StringBuilder sb){
if(root == null){
return ;
}
sb.append(root.val);
if(root.left != null){
sb.append("(");
treeToStr(root.left,sb);
sb.append(")");
}else{
if(root.right == null){
return ;
}else{
sb.append("()");
}
}
if(root.right != null){
sb.append("(");
treeToStr(root.right,sb);
sb.append(")");
}else{
return ;
}
}
}
Original: https://blog.csdn.net/m0_63979882/article/details/128298928
Author: 学Java的冬瓜
Title: 【Java 数据结构】-二叉树OJ题
原创文章受到原创版权保护。转载请注明出处：https://www.johngo689.com/787132/
转载文章受原作者版权保护。转载请注明原作者出处！