java黑洞网 首页 博客 问答 站长公众号 pdf 视频 游戏 脚本 实战 其它资源
写博客 注册

程序员最近都爱上了这个网站  程序员们快来瞅瞅吧！  it98k网:it98k.com

本站消息

站长简介/公众号

  出租广告位,需要合作请联系站长


+关注
已关注

分类  

暂无分类

标签  

暂无标签

日期归档  

2023-06(2)

[Java]快速入门二叉树,手撕相关面试题

发布于2022-09-18 17:03     阅读(263)     评论(0)     点赞(18)     收藏(2)

专栏简介 :java语法及数据结构

题目来源:leetcode,牛客,剑指offer

创作目标:从java语法角度实现底层相关数据结构,达到手撕各类题目的水平.

希望在提升自己的同时,帮助他人,,与大家一起共同进步,互相成长.

学历代表过去,能力代表现在,学习能力代表未来!

目录

前言

一>树形结构

1.树的概念

2.树的应用

二>二叉树

1.二叉树的概念

 2.两种特殊的二叉树

3.二叉树的性质

4.二叉树的存储

5.二叉树的创建

6.二叉树的遍历

1)前序遍历

2)中序遍历

3)后序遍历 

4)层序遍历

5)子问题思路与遍历思路的区别 

6)leetcode提交做法

三 >二叉树常见面试题

1.选择题部分:

2.编程题部分:

1.节点个数

2.叶子节点个数

3.获取二叉树第K层节点的个数

4.二叉树的高度

5.检测值为value的元素是否存在

6.判断一棵树是不是完全二叉树(栈)

7.相同的树

8.另一棵树的子树

9.平衡二叉树(字节跳动原题)

10.对称二叉树

11.创建二叉树

12.二叉树的最近公共祖先

13.二插搜索树转双向链表

14.从前序遍历到中序遍历构造二叉树

15.从中序遍历到后序遍历构造二叉树

16.根据二叉树创建字符串

17.前序遍历非递归写法

18.中序遍历非递归写法

19.后序遍历非递归写法

总结>

前言

        本文主要讲解二叉树重点知识很少涉及无关的背景知识,旨在即快速又清晰熟练掌握二叉树并手撕相关面试题,希望我的文章能对你有所帮助与启发.

一>树形结构

1.树的概念

         学习二叉树之前我们首先要了解树形结构,树是一种非线性结构,它是由n(n>=0)个有限节点组成的的具有层次关系的集合,之所以把它叫做树,是因为该结构看起来像是一颗倒挂的树.树具有以下特点:

  • 树的根节点无前驱节点
  • 其余节点有且仅有一个前驱,但有多个后继
  • 树是由递归定义的

重要概念:

  • 节点的度:一个节点含有的子节点的个数叫做节点的度,如上图中A的度为7.
  • 树的度:一个树中,最大节点的度称为树的度,如上图数的度为7.
  • 叶子节点:度数为0的节点叫叶子节点
  • 父节点:若一个节点有子节点,则这个节点称为其子节点的父节点.
  • 根节点:一个树种,无父节点的节点.如A
  • 节点的层次:从根开始定义,根为第一层,根的子节点为第二层,以此类推.
  • 树的深度与高度:树的深度是从根节点开始（其深度为1）自顶向下逐层累加的；而二叉树高度是从叶节点开始（其高度为1）自底向上逐层累加的。虽然树的深度和高度一样，但是具体到树的某个节点，其深度和高度是不一样

2.树的应用

我们平时使用的各种文件系统管理,其底层逻辑都是树形结构.

二>二叉树

1.二叉树的概念

在树形结构的基础上二叉树有两个特点:

  • 每个节点最多两颗子树,即二叉树不存在度数大于二的节点.
  • 每个二叉树的子树有左右之分,其子树的次序不能颠倒,因此二叉树是有序树.

 2.两种特殊的二叉树

  • 满二叉树:每一层的节点数都达到最大值就是满二叉树.
  • 完全二叉树:完全二叉树是效率很高的数据结构,每一个节点与树中编号一一对应,所以满二叉树是一种特殊的完全二叉树. 

3.二叉树的性质

  • 若规定根节点的层数为1,则一颗非空二叉树的第i层有有 2^{i-1}(i>0)个节点.
  • 若规定根节点的二叉树的深度为1,则深度为k的二叉树的最大节点个数2^k-1(k>=0).
  • 对任何一颗二叉树,如果其叶子节点个数为n0,其度数为2的非叶子节点的个数为n2,那么        n0=n2+1.证法如下(1)
  • 具有n个节点的完全二叉树的深度为\log_{2} (n+1)向上取整.证法如下(2)
  • 对于有n个节点的完全二叉树,如果按照从上到下从左到右的顺序对所以有节点从0开始编号,则对于序号为i的节点有:
    • 若i>0双亲序号为:(i/2)-1.
    • 若2i+1<n,左孩子序列为2i+1,否则无左孩子.
    • 若2i+2<n,右孩子序列为2i+2,否则无右孩子.

证(1):>

  1. 设二叉树顶点数=N,度数为0的节点为n0,度数为1的节点为n1,度数为2的为n2.
  2. 度数和=顶点数(N)-1.(度数和 = N-1)
  3. 顶点数(N) = n0+n1+n2.
  4. 度数和 = 0*n0+1*n1+2*n2.
  5. 结合2,3,4可得:0*n0+1*n1+2*n2 = n0+n1+n2-1
  6. 化简得:n0 = n2+1

 证(2):>

  • 深度为1的节点数2^{0},深度为2的节点数为2^{1}.....深度为k的节点数为2^{k-1},由等比数列        求和公式:   {\color{Red} \frac{1-2^{n}}{1-2}   .那么节点数为n的深度为{\color{Magenta} \log_{2}n+1}.

4.二叉树的存储

        二叉树的存储结构分为顺序存储和类似于链表的链式存储,本章采用链式存储.表示方法采用孩子表示法,即一个节点中包含数据域,左孩子与右孩子.

  1. class Node {
  2. int val; // 数据域
  3. Node left; // 左孩子的引用，常常代表左孩子为根的整棵左子树
  4. Node right; // 右孩子的引用，常常代表右孩子为根的整棵右子树
  5. }

5.二叉树的创建

二叉树的创建需要三步:

  1. 创建结点:包含数值域,左孩子结点,右孩子结点
  2. 创建二叉树:我们采用前序遍历+递归的方式创建二叉树.
  3. 输入要创建的序列:本文二叉树的物理连接方式是链表,所以我们采用LinkedList集合存储二叉树内容.使用asList方法写入数组.

  1. class TreeNode{//二叉树节点
  2.    int data;
  3.    TreeNode1 leftChild;
  4.    TreeNode1 rightChild;
  5.  
  6.     public TreeNode1(int data) {
  7.         this.data = data;
  8.     }
  9. }
  10. public static TreeNode createBinaryTree(LinkedList<Integer> inputList){//创建二叉树
  11.         TreeNode node = null;
  12.         if (inputList==null||inputList.isEmpty()){
  13.             return null;
  14.         }
  15.         Integer data = inputList.removeFirst();//每次取出集合中的第一个元素
  16.         //这里判空很重要,如果元素为空,则不在进一步递归.
  17.         if (data!=null){
  18.             node = new TreeNode1(data);
  19.             node.leftChild = createBinaryTree(inputList);
  20.             node.rightChild = createBinaryTree(inputList);
  21.         }
  22.         return node;
  23.     }
  24. public static void main(String[] args) {
  25.         LinkedList<Integer> inputList = new LinkedList<>        
  26.         (Arrays.asList(3,2,9,null,null,10,null,null,8,null,4));
  27.         TreeNode1 treeNode1 = createBinaryTree(inputList);
  28.     }

6.二叉树的遍历

        初学二叉树时,许多同学会很疑惑二叉树为什么需要这么多的遍历方法?

1)前序遍历

  1. public static void preOrderTraveral(TreeNode node){//to前序遍历
  2.         if (node==null){
  3.             return;
  4.         }
  5.         System.out.print(node.data+" ");
  6.         preOrderTraveral(node.leftChild);
  7.         preOrderTraveral(node.rightChild);
  8.     }

2)中序遍历

  1. public static void midOrderTraveral(TreeNode node){//中序遍历
  2.         if (node==null){
  3.             return;
  4.         }
  5.         midOrderTraveral(node.leftChild);
  6.         System.out.print(node.data+" ");
  7.         midOrderTraveral(node.rightChild);
  8.     }

3)后序遍历 

  1. public static void lastOrderTraveral(TreeNode node){//后序遍历
  2.         if (node==null){
  3.             return;
  4.         }
  5.         lastOrderTraveral(node.leftChild);
  6.         lastOrderTraveral(node.rightChild);
  7.         System.out.print(node.data+" ");
  8.     }

4)层序遍历

  1.   public static void levelOrderTraveral(TreeNode root) {//层序遍历
  2.         Queue<TreeNode> queue = new LinkedList<>();
  3.         queue.offer(root);
  4.         while (!queue.isEmpty()){
  5.             TreeNode node = queue.poll();
  6.             System.out.println(node.data);
  7.             if (node.leftChild!=null){
  8.                 queue.offer(node.leftChild);
  9.             }
  10.             if (node.rightChild!=null){
  11.                 queue.offer((node.rightChild));
  12.             }
  13.         }
  14.     }

5)子问题思路与遍历思路的区别 

        许多初学二叉树的同学,可能无法很好的理解子问题思路与遍历思路的区别,导致许多题目一知半解.下面我们详细讲解一下子问题思路与遍历思路.假设我们要求一颗二叉树所有节点的个数.

  • 遍历思路:定义一个变量count记录节点个数,每遍历一个节点count++,最后返回count即可.
  • 子问题思路:将二叉树看成由许多个小的二插树组成.每个小树算完再返回给上一层的大树.

  1. class Solution {//遍历思路
  2.     int count = 0;
  3.     public int countNodes(TreeNode root) {
  4.         if(root==null){
  5.             return 0;
  6.         }
  7.             count++;
  8.             countNodes(root.left);
  9.             countNodes(root.right);
  10.     return count;
  11.   }
  12. }
  1. class Solution {//子问题思路拆解写法
  2.     public int countNodes(TreeNode root) {
  3.         if(root==null){
  4.             return 0;
  5.         }
  6.         int leftTreeCount = countNodes(root.left);
  7.         int rightTreeCount = countNodes(root.right);
  8.         return leftTreeCount+rightTreeCount+1;
  9.     }
  10. }

6)leetcode提交做法

        在leetcode中刷题我们发现,无论是哪种遍历方式都需要返回一个List集合类型的值,也就是将二叉树的信息存在集合中并返回.这里提供两种思路:

  • 遍历思路:如果在二叉树的类中new一个List对象,那么每次遍历都会new对象,很显然这样做无法返回所有对象,所以我们只需将List集合创建在前序遍历类外,不断的遍历二叉树向集合中添加元素,最后返回存好的对象即可.
  • 子问题思路:如果每次遍历二叉树都会创建新的对象,那么我们可以把所有创建出的对象,分为左右子树,最终加和到一个对象里返回即可.

  1.     List<Integer> relist = new ArrayList<Integer>();//集合创建在类外
  2.     public List<Integer> preorderTraversal(TreeNode root) {//遍历思路
  3.         if(root==null){
  4.             return relist;
  5.         }
  6.         relist.add(root.val);
  7.         preorderTraversal(root.left);
  8.         preorderTraversal(root.right);
  9.         return relist;
  10.     }
  1. public List<Integer> preorderTraversal(TreeNode root) {//子问题思路
  2.         List<Integer> relist = new ArrayList<Integer>();
  3.         if(root==null){
  4.             return relist;
  5.         }
  6.         relist.add(root.val);
  7.         List<Integer> leftTree = preorderTraversal(root.left);
  8.         relist.addAll(leftTree);//所有的左树
  9.         List<Integer> rigthTree = preorderTraversal(root.right);
  10.         relist.addAll(rigthTree);//所有的右树
  11.         return relist;
  12.     }

        leetcode中层序遍历的提交方法更为特殊,需要返回一个List集合的二维数组.只需每遍历一层二叉树就存进一个一维数组中,最后将所有一位数组存进二维数组中返回即可.

  1. public List<List<Integer>> levelOrder(TreeNode root) {
  2.         List<List<Integer>> ret = new ArrayList();
  3.         if(root==null) return ret;
  4.         Queue<TreeNode> queue = new LinkedList<>();
  5.         queue.offer(root);
  6.         while(!queue.isEmpty()){
  7.             int size = queue.size();
  8.             List<Integer> list = new ArrayList<>();
  9.             while(size!=0){
  10.                 TreeNode cur = queue.poll();
  11.                 if(cur.left!=null){
  12.                     queue.offer(cur.left);
  13.                 }
  14.                 if(cur.right!=null){
  15.                     queue.offer(cur.right);
  16.                 }
  17.                 size--;
  18.                 list.add(cur.val);
  19.             }
  20.             ret.add(list);
  21.         }
  22.         return ret;
  23.  
  24.     }

三 >二叉树常见面试题

1.选择题部分:

1.1 某二叉树公有399个节点,其中有199个度为2的节点,则该二叉树中子节点的个数为().

A.200                      B.198                          C.199                       D.不存在这样的二叉树

由上文已知,n0 = n2+1.那么199个2度节点就对应198个0度节点.(B)

1.2 在具有2n个节点的完全二叉树中,子节点个数为()

A.n                          B.n+1                          C.n-1                        D.n/2            

2n个节点说明节点数一定是偶数, 那么该二叉树n1 = 1(只有一个一度点),根据定理可知n0 = n2+1.设子节点个数为x,那么2n = n0+1+n2可写为:2n = 2x,化简得:x = n. (A)

 1.3  一个具有767个节点的完全二叉树,其叶子节点个数为多少()

A.383                      B.384                          C.385                        D.386

由上文已知767个节点为奇数,那么一定没有1度的节点,根据定理 n0 = n2+1,设子节点个数为x,那么767 = n0+n2可写为:2x-1,化简得x = 384. (B)

 1.4 一颗完全二叉树的节点个数为531,那么这棵树的高度为()

A.11                         B.10                            C.8                            D.12 

 由定理具有n个节点的完全二叉树深度为:\log_{2} (n+1)向上取整,所以我们需要估算\log_{2}532,答案比9大但比10小,基于向上取整的原则我们选择10. (B)

1.5 二叉树的前序遍历和中序遍历如下:前序遍历:EFHIGJK;中序遍历:HFIEJKG,则二叉树的根节点为()

A.E                           B.F                              C.G                            D.H

前序遍历确定根节点为E,中序遍历确定二叉树的分布为:左树HFI,右树:JKG.(E)

1.6 设一颗二叉树的中序遍历序列:badce,后序遍历:bdeca,则二叉树前序遍历序列为()

A.adbce                  B.decab                        C.debac                    D.abcde

后续遍历确定二叉树的根节点位a,中序遍历确定二叉树的分布为:左树b,右树为dce.由后续遍历的规则画好二叉树后得前序遍历为abcde.

1.7 某二叉的后序遍历和中序遍历序列相同,均为ABCDEF,则按层序输出的序列为()

A.FEDCBA             B.CBAFED                   C.DEFCBA                D.ABCDEF 

 后续遍历确定根节点为F,中序遍历确定节点全部在左树,根据后续遍历的规则画出图:

按层序输出为FEDCBA. (A)

2.编程题部分:

1.节点个数

此题变相考察二叉树的遍历方式,只要会遍历二叉树即可得出结果.博主提供两种思路:遍历思路和子问题思路.上文已对子问题思路和遍历思路详细的解析这里不过多赘述.

  1. class Solution {//子问题思路
  2.     public int countNodes(TreeNode root) {
  3.         if(root==null){
  4.             return 0;
  5.         }
  6.         return countNodes(root.left)+countNodes(root.right)+1;
  7.     }
  8. }
  9. class Solution {//子问题思路拆解写法
  10.     public int countNodes(TreeNode root) {
  11.         if(root==null){
  12.             return 0;
  13.         }
  14.         int leftTreeCount = countNodes(root.left);
  15.         int rightTreeCount = countNodes(root.right);
  16.         return leftTreeCount+rightTreeCount+1;
  17.     }
  18. }
  1. class Solution {//遍历思路
  2.     int count = 0;
  3.     public int countNodes(TreeNode root) {
  4.         if(root==null){
  5.             return 0;
  6.         }
  7.             count++;
  8.             countNodes(root.left);
  9.             countNodes(root.right);
  10.     return count;
  11.   }
  12. }

2.叶子节点个数

与节点个数写法一致,只不过记录数据的条件改为:当左右节点都为空时++.依旧是两种思路:

  1. public static int getLeafNodeCount(TreeNode root){//完全二叉树叶子节点个数 遍历思路
  2.         if (root==null){
  3.             return 0;
  4.         }
  5.         if (root.leftChild==null&&root.rightChild==null){
  6.             count++;
  7.         }
  8.         getLeafNodeCount(root.leftChild);
  9.         getLeafNodeCount(root.rightChild);
  10.         return count;
  11.     }
  1.  public static int getLeafNodeCount1(TreeNode root){//完全二叉树叶子节点个数 子问题思路
  2.         if (root==null){
  3.             return 0;
  4.         }
  5.         if (root.leftChild==null&&root.rightChild==null){
  6.             return 1;
  7.         }
  8.         return getLeafNodeCount(root.leftChild)+getLeafNodeCount(root.rightChild);
  9.     }

3.获取二叉树第K层节点的个数

该题使用子问题思路,重点是如何找到第K层?我们可以逆向来思考,如果让我们找第三层,我们可以假设第一层为3,每下一层就减1,当k==1时找到第三层.

 

  1. public static int getLevelNodeCount(TreeNode root,int k){//获取第k层节点的个数
  2.         if(root==null||k<=0){
  3.             return 0;
  4.         }
  5.         if (k==1){
  6.             return 1;
  7.         }
  8.         return getLevelNodeCount(root.leftChild,k-1)
  9.                 +getLevelNodeCount(root.rightChild,k-1);
  10.     }

4.二叉树的高度

该题使用子问题思路,由于可能出现左树或右树为空另一颗树不为空的情况,所以我们可以比较左树和右树的高度,返回最大的即可.

 

  1. public static int getHeight(TreeNode root){//获取二叉树的高度
  2.         if (root==null){
  3.             return 0;
  4.         }
  5.         int leftHeight = getHeight(root.leftChild);
  6.         int rightHeight = getHeight(root.rightChild);
  7.         return leftHeight>rightHeight?leftHeight+1:rightHeight+1;
  8.     }

5.检测值为value的元素是否存在

该题为遍历思路,设置好递归的结束条件:节点为空或者节点的值为要查找的值.

  1. public static TreeNode find(TreeNode root,char val){//检测value元素是否存在
  2.         if (root==null){
  3.             return null;
  4.         }
  5.         if (root.data==val){
  6.             return root;
  7.         }
  8.         TreeNode retLeft = find(root.leftChild,val);//先去左树找
  9.         if (retLeft!=null){//说明找到了
  10.             return retLeft;
  11.         }
  12.         TreeNode retRight = find(root.rightChild,val);//再去右树找
  13.         if (retRight!=null){//说明找到了
  14.             return retRight;
  15.         }
  16.         return null;
  17.     }

6.判断一棵树是不是完全二叉树(栈)

由之前的知识可知,完全二叉树每一个节点都与树中编号对应,说明一定是有顺序的.说到顺序我们首先要考虑栈和队列这两种数据结构.判断是不是完全二叉树,当一个节点没有利用价值时要立刻弹出,所以队列头进头出的方式最为合适.如下图所示,如果是完全二叉树那么队列中的空元素一定是连续的.

  1.  public static boolean isCompleteTree1(TreeNode root){//判断是不是完全二叉树,队列
  2.         if (root==null)return true;
  3.         Queue<TreeNode> queue = new LinkedList<>();
  4.         queue.offer(root);
  5.         while (!queue.isEmpty()){
  6.             TreeNode cur = queue.poll();
  7.             if (cur!=null){
  8.                 queue.offer(cur.leftChild);
  9.                 queue.offer(cur.rightChild);
  10.             }else {
  11.                 break;
  12.             }
  13.         }
  14.         while (!queue.isEmpty()){
  15.             if (queue.poll()!=null){
  16.                 return false;
  17.             }
  18.         }
  19.         return true;
  20.     }

7.相同的树

该题为子问题思路,做法为排除所有错误情况,剩余正确的.相同的树指的是,节点的值相同且树的结构也是相同的.

时间复杂度O(min(m,n)){左树节点个数为m,右树节点个数为n}

  1. public boolean isSameTree(TreeNode p, TreeNode q) {
  2.         if(p==null&&q!=null)return false;
  3.         if(p!=null&&q==null)return false;
  4.         if(p==null&&q==null)return true;
  5.         if(p.val!=q.val){
  6.             return false;
  7.         }
  8.         return isSameTree(p.left,q.left)&&isSameTree(p.right,q.right);
  9.     }

8.另一棵树的子树

该题建立在判断两颗树是否相同的基础上,运用子问题思路,先判断根节点是不是子树,如果没有再判断左子树中有没有子树,如果没有再判断右子树中有没有子树.

 时间复杂度O(m*n)

本质判断相同

  1. public boolean isSameTree(TreeNode p, TreeNode q) {
  2.         if(p==null&&q!=null)return false;
  3.         if(p!=null&&q==null)return false;
  4.         if(p==null&&q==null)return true;
  5.        
  6.         if(p.val!=q.val){
  7.             return false;
  8.         }
  9.         return isSameTree(p.left,q.left)&&isSameTree(p.right,q.right);
  10.     }
  11.     public boolean isSubtree(TreeNode root, TreeNode subRoot) {
  12.         if(root==null||subRoot==null){
  13.             return false;
  14.         }
  15.         //判断是否是相同的树
  16.         if(isSameTree(root,subRoot)){
  17.             return true;
  18.         }
  19.         //判断是不是左子树
  20.         if(isSubtree(root.left,subRoot)){
  21.             return true;
  22.         }
  23.         //判读是否是右子树
  24.         if(isSubtree(root.right,subRoot)){
  25.             return true;
  26.         }
  27.         //既不是左子树,也不是右子树,且不相同
  28.         return false;
  29.     }

9.平衡二叉树(字节跳动原题)

该题为子问题思路,需要之前判断二叉树高度的知识,一棵树如果是平衡二叉树那么其子树也一定是平衡二叉树,本质就是判断所有子树的高度差是否大于1.由于该题较为经典,所以提供两种做法不同的做法.

时间复杂度O(N^2)

遍历每一个子树,如果高度差<=1,返回true.但是该方法要为每一个节点都计算高度,时间复杂度大大增加.

  1. public int height (TreeNode root){
  2.         if(root==null){
  3.             return 0;
  4.         }
  5.         int leftHeight = height(root.left);
  6.         int rightHeight = height(root.right);
  7.         return leftHeight>rightHeight?(leftHeight+1):(rightHeight+1);
  8.     }
  9.     public boolean isBalanced(TreeNode root) {
  10.         if(root==null){
  11.             return true;
  12.         }
  13.         int leftHeight = height(root.left);
  14.         int rightHeight = height(root.right);
  15.         return Math.abs(leftHeight-rightHeight)<=1&&isBalanced(root.left)&&isBalanced(root.right);
  16.  
  17.     }

时间复杂度O(N)

改进方法是如果父亲节点已经计算过高度那么子节点无需再次遍历.如果左右子树的高度差>1说明不是平衡二叉树,那么将不断递归返回-1.如果是平衡二叉树那么一定会返回一个正数,所以我们只需判断返回值的正负即可.

  1. public int height (TreeNode root){
  2.         if(root==null){
  3.             return 0;
  4.         }
  5.         int leftHeight = height(root.left);
  6.         int rightHeight = height(root.right);
  7.         if(leftHeight>=0&&rightHeight>=0&&Math.abs(leftHeight-rightHeight)<=1){
  8.            return leftHeight>rightHeight?(leftHeight+1):(rightHeight+1);
  9.         }else{
  10.             return -1;
  11.         }
  12.     }
  13.     public boolean isBalanced(TreeNode root) {
  14.         if(root==null){
  15.             return true;
  16.         }
  17.        return height(root)>=0;
  18.     }

10.对称二叉树

 该题为子问题思路,对称二叉树要求左右子树对称的部分值相同,很明显一个参数的函数无法同时比较两颗子树,所以我们需要构造一个两个参数的函数,分别比较左树的左与右树的右.

  1. public boolean isSymmetricChild(TreeNode rootleft,TreeNode rootrigth){
  2.         
  3.         if(rootleft==null&&rootrigth!=null){
  4.             return false;
  5.         }
  6.         if(rootleft!=null&&rootrigth==null){
  7.             return false;
  8.         }
  9.         if(rootleft==null&&rootrigth==null){
  10.             return true;
  11.         }
  12.         if(rootleft.val!=rootrigth.val){
  13.             return false;
  14.         }
  15.         return isSymmetricChild(rootleft.left,rootrigth.right)&&isSymmetricChild(rootleft.right,rootrigth.left);
  16.     }
  17.     public boolean isSymmetric(TreeNode root) {
  18.         if(root==null){
  19.             return true;
  20.         }
  21.         return isSymmetricChild(root.left,root.right);
  22.     }

11.创建二叉树

 该题主要分为三部分:创建结点,创建二叉树,中序遍历输出.创建结点与中序遍历上文已经提到过,创建二叉树时采用前序遍历的思想也可以很容易写出.

  1. import java.util.*;
  2.  
  3. class TreeNode{//创建结点
  4.     public char val;
  5.     public TreeNode left;
  6.     public TreeNode right;
  7.     public TreeNode(char val){
  8.         this.val = val;
  9.     }
  10. }
  11. public class Main{
  12.     public static int i = 0;
  13.     public static TreeNode createTree(String str){//创建二叉树
  14.         TreeNode root = null;
  15.         if(str.charAt(i)!='#'){
  16.             root = new TreeNode(str.charAt(i));
  17.             i++;
  18.             root.left = createTree(str);
  19.             root.right = createTree(str);
  20.         }else{
  21.             i++;
  22.         }
  23.         return root;
  24.     }
  25.     public static void inorder(TreeNode root){//中序遍历
  26.         if(root==null){
  27.             return ;
  28.         }
  29.         inorder(root.left);
  30.         System.out.print(root.val+" ");
  31.         inorder(root.right);
  32.     }
  33.     public static void main(String[] args){
  34.         Scanner in = new Scanner(System.in);
  35.         while(in.hasNextLine()){
  36.             String str = in.nextLine();
  37.             TreeNode root = createTree(str);
  38.             inorder(root);
  39.         }
  40.     }
  41. }

12.二叉树的最近公共祖先

该题为子问题思路,先写明结束条件:节点等于空返回空节点,节点为根节点直接返回节点.然后去遍历左树与右树,判断返回值的三种情况:

  1. 节点分布在左右树两侧,即返回值都不为空,那么公共祖先一定是根节点.
  2. 节点分布在右侧,即返回值为第一个遇到的节点,那么公共祖先为第一个遇到的节点.
  3. 节点分布在右侧同理.

  1. public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
  2.         if(root==null) return null;
  3.         if(root==p||root==q){
  4.             return root;
  5.         }
  6.         TreeNode leftT = lowestCommonAncestor(root.left,p,q);
  7.         TreeNode rightT = lowestCommonAncestor(root.right,p,q);
  8.         if(leftT!=null&&rightT!=null){
  9.             return root;
  10.         }else if(leftT!=null){
  11.             return leftT;
  12.         }else{
  13.             return rightT;
  14.         }
  15.     }

假设这颗二叉树使用孩子双亲表示法:那么该问题就可以转化为双向链表求焦点,先让较长的链表走长度的差值步,两个链表长度相同时一边向前走一边判断值是否相同,值相同的节点即为公共祖先.但该题使用的是孩子表示法,无法得知上一个节点是谁,所以只能将节点的路径保存下来,而路径又是有序的,提到顺序我们想到栈和队列,我们需要从后向前找公共节点,很明显需要用栈来保存,而一个栈只能保存一个节点的路径,所以我们需要两个栈.保存好如图所示的路径后,让栈内元素多的先pop(),直到两个栈元素个数相同,然后两个栈一边出元素一边比较元素,遇到相同的就是公共节点.现在最关键的问题就是如何在栈内保存指定的路径?我们可以构造一个储存路径的函数,比较目标节点node和根节点root的关系不断更新路径.栈内路径保存完毕后,就是出栈操作相对简单,这里不过多赘述.

  1. public boolean getPath(TreeNode root,TreeNode node,Stack<TreeNode>stack){
  2.         if(root==null||node==null){
  3.             return false;
  4.         }
  5.         stack.push(root);
  6.         if(root==node){
  7.             return true;
  8.         }
  9.         boolean flg = getPath(root.left,node,stack);
  10.         if(flg==true){
  11.             return true;
  12.         }
  13.         flg = getPath(root.right,node,stack);
  14.         if(flg==true){
  15.             return true;
  16.         }
  17.         stack.pop();
  18.         return false;
  19.     }
  20.     public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
  21.         if(root==null) return null;
  22.         Stack<TreeNode> stack1 = new Stack<>();
  23.         getPath(root,p,stack1);
  24.         Stack<TreeNode> stack2 = new Stack<>();
  25.         getPath(root,q,stack2);
  26.  
  27.         int size1 = stack1.size();
  28.         int size2 = stack2.size();
  29.         if(size1>size2){
  30.             int size = size1-size2;
  31.             while(size!=0){
  32.                 stack1.pop();
  33.                 size--;
  34.             }
  35.             while(!stack1.isEmpty()&&!stack2.isEmpty()){
  36.                 if(stack1.peek()==stack2.peek()){
  37.                     return stack1.pop();
  38.                 }else{
  39.                     stack1.pop();
  40.                     stack2.pop();
  41.                 }
  42.             }
  43.         }else{
  44.             int size = size2-size1;
  45.             while(size!=0){
  46.                 stack2.pop();
  47.                 size--;
  48.             }
  49.             while(!stack1.isEmpty()&&!stack2.isEmpty()){
  50.                 if(stack1.peek()==stack2.peek()){
  51.                     return stack2.pop();
  52.                 }else{
  53.                     stack1.pop();
  54.                     stack2.pop();
  55.                 }
  56.             }
  57.         }
  58.         return null;
  59.     }

13.二插搜索树转双向链表

该题为遍历思路,难点在于如何在中序遍历的过程中修改指向,首先我们确定递归的结束条件为节点为空,当节点为null时说明我们此时找到了中序遍历的第一个节点(4),此时我们可以修改节点的指向让它的left指向null,再去遍历左树左树也为null,返回到节点(6),此时应该让(6)的左指向(4),再让(4)的右指向(6),但我们已经找不到(4)这个节点了,所以为了记录节点可以在函数外定义成员遍历prev记录node的值,但在第一个节点时不需要这一步操作,因为prev初始值为null,prev.right会出现空指针异常.

  1. TreeNode prev = null;
  2.     public void inOrder(TreeNode node){
  3.         if(node==null) return;
  4.         inOrder(node.left);
  5.         //打印
  6.         node.left = prev;
  7.         if(prev!=null){
  8.             prev.right = node;
  9.         }
  10.         prev = node;
  11.         inOrder(node.right);
  12.     }
  13.     public TreeNode Convert(TreeNode pRootOfTree) {
  14.         if(pRootOfTree==null) return null;
  15.         inOrder(pRootOfTree);
  16.         TreeNode head = pRootOfTree;
  17.         while(head.left!=null){
  18.             head = head.left;
  19.         }
  20.         return head;
  21.     }

14.从前序遍历到中序遍历构造二叉树

该题为子问题思路,首先要明白的是前序遍历用来确定每一颗子树根节点,中序遍历用来确定二叉树的构造情况并创建二叉树, 

  1. int preIndex = 0;
  2.     public TreeNode creativePbyI(int[] preorder, int[] inorder,int beging,int end){
  3.         if(beging>end){
  4.             return null;
  5.         }
  6.         TreeNode root = new TreeNode(preorder[preIndex]);
  7.         int rootIndex = findIndex(inorder,beging,end,preorder[preIndex]);
  8.         if(rootIndex==-1){
  9.             return null;
  10.         }
  11.         preIndex++;
  12.         root.left = creativePbyI(preorder,inorder,beging,rootIndex-1);
  13.         root.right = creativePbyI(preorder,inorder,rootIndex+1,end);
  14.         return root;
  15.     }
  16.     public int findIndex( int[] inorder,int beging,int end,int key){
  17.         for(int i = 0;i<=end;i++){
  18.             if(inorder[i]==key){
  19.                 return i;
  20.             }
  21.         }
  22.         return -1;
  23.     }
  24.     public TreeNode buildTree(int[] preorder, int[] inorder) {
  25.         if(preorder==null||inorder==null){
  26.             return null;
  27.         }
  28.         return creativePbyI(preorder,inorder,0,preorder.length-1);
  29.     }

15.从中序遍历到后序遍历构造二叉树

做法与上一题类似,更改函数名即可. 

  1. int postIndex = 0;
  2.     public TreeNode creativePbyI(int[] inorder, int[] postorder,int beging,int end){
  3.         if(beging>end){
  4.             return null;
  5.         }
  6.         TreeNode root = new TreeNode(postorder[postIndex]);
  7.         int rootIndex = findIndex(inorder,beging,end,postorder[postIndex]);
  8.         if(rootIndex==-1){
  9.             return null;
  10.         }
  11.         postIndex--;
  12.         root.right = creativePbyI(inorder,postorder,rootIndex+1,end);
  13.         root.left = creativePbyI(inorder,postorder,beging,rootIndex-1);
  14.         return root;
  15.     }
  16.     public int findIndex( int[] inorder,int beging,int end,int key){
  17.         for(int i = 0;i<=end;i++){
  18.             if(inorder[i]==key){
  19.                 return i;
  20.             }
  21.         }
  22.         return -1;
  23.     }
  24.     
  25.     public TreeNode buildTree(int[] inorder, int[] postorder) {
  26.         if(postorder==null||inorder==null){
  27.             return null;
  28.         }
  29.         postIndex = postorder.length-1;
  30.         return creativePbyI(inorder,postorder,0,inorder.length-1);
  31.     }

16.根据二叉树创建字符串

本题考察了对二叉树递归的应用与字符串拼接相关的知识,按题意我们分析出可能出现的所有情况,由于是前序遍历,所以我们先从左树的情况来判断,先拼接一个元素当t.left!=null时加"(",并继续递归.当t.left=null&&t.right=null时直接retrun,回溯到上一步会再加一个")",当t.left=null&&t.right!=null加"()".如果左树遍历完我们再去遍历右树t,right!=null加"(",t.right=null时直接返回.

  1. public void treeToString(TreeNode t,StringBuffer sb){
  2.         if(t==null){
  3.             return;
  4.         }
  5.         sb.append(t.val);
  6.         if(t.left!=null){
  7.             sb.append("(");
  8.             treeToString(t.left,sb);
  9.             sb.append(")");
  10.         }else{
  11.             //t.left==null
  12.             if(t.right==null){
  13.                 return;
  14.             }else{
  15.                 sb.append("()");
  16.             }
  17.         }
  18.         if(t.right!=null){
  19.             sb.append("(");
  20.             treeToString(t.right,sb);
  21.             sb.append(")");
  22.         }else{
  23.             return;
  24.         }
  25.  
  26.     }
  27.     public String tree2str(TreeNode root) {
  28.         if(root==null) return null;
  29.         StringBuffer sb = new StringBuffer();
  30.         treeToString(root,sb);
  31.         return sb.toString();
  32.     }

17.前序遍历非递归写法

牵扯到顺序就考虑栈和队列,前序遍历遍历完左树后需要回溯到右树继续遍历,所以必须保存它的路径,方便后续回溯,那么用栈最为合适.

  1. public static void preOrderTraveralWithStack(TreeNode root){//非递归前序遍历
  2.         Stack<TreeNode> stack = new Stack<TreeNode>();
  3.         TreeNode node = root;
  4.         while (node!=null||!stack.isEmpty()){
  5.             while (node!=null){
  6.                 System.out.println(node.data);
  7.                 stack.push(node);
  8.                 node = node.leftChild;
  9.             }
  10.             if(!stack.isEmpty()){
  11.                 node = stack.pop();
  12.                 node = node.rightChild;
  13.             }
  14.         }
  15.     }

18.中序遍历非递归写法

与前序遍历写法一致,不过更改打印元素位置,当中序遍历元素被弹出时打印.

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

19.后序遍历非递归写法

与中序遍历不同的是,后续遍历到cur.left=null时必须确保cur.right=null才能弹出cur.所以只能peek(）栈顶的元素看它的右树是否存在,不存在就弹出,存在还需遍历右树.但此时会出现一个为问题,右树的遍历会陷入死循环.所以需要对右树的遍历加限制条件,如果右树已经遍历或者右树为空,可以直接弹出.因此当右树遍历后就用prev来记录top节点,如果prev=top说明已经遍历过,直接弹出即可.

  1. public List<Integer> postorderTraversal(TreeNode root) {
  2.         List<Integer> ret = new ArrayList<>();
  3.         if(root==null) return ret;
  4.         Stack<TreeNode> stack = new Stack<>();
  5.         TreeNode cur = root;
  6.         TreeNode prev = null;
  7.         while(cur!=null||!stack.isEmpty()){
  8.             while(cur!=null){
  9.             stack.push(cur);
  10.             cur = cur.left;
  11.         }
  12.         TreeNode top = stack.peek();
  13.         if(top.right==null||top.right==prev){
  14.             stack.pop();
  15.             ret.add(top.val);
  16.             prev = top;//记录最近一次遍历二叉树
  17.         }else{
  18.             cur = top.right;
  19.         }
  20.     }
  21.     return ret;
  22.    }

总结>

        以上就是快速入门二叉树的全部内容,从最基础知识到手撕面试题,认真看完的同学可能会发现,二叉树的知识点非常综合,稍有难度的题不仅涉及到之前数据结构的知识,还会牵连到一些二叉树的子问题.码字不易耗时半月,如果对你的学习有所启发,麻烦不要忘记三连哦!

原文链接:https://blog.csdn.net/liu_xuixui/article/details/126138054

2022年最受欢迎的8大编程语言

为什么都说程序员找不到女朋友，但是身边程序猿的却没一个单身的

30岁以上你还死磕技术，别说拿高薪，可能你连饭碗都会保不住

程序员被开除，老板：“有你参与的项目全黄了！”

笑话：一个测试工程师走进一家酒吧

趣图：程序员头疼的4种原因

笑话：面试官：请拿出一段体现你水平的代码。我： sudo rm -rf /*面试官：这体现了你哪方面能力？

java精选：SSO单点登录】JWT入门概述&&残留的安全问题

网友说：做开发，不被领导喜欢怎么办？

网友说：我奉劝各位，一定不能在职场透露自己的家庭条件



所属网站分类: 技术文章 > 博客

作者：zhqu4399

链接：http://www.javaheidong.com/blog/article/504377/046a6c86c5b3376a7eca/

来源：java黑洞网

任何形式的转载都请注明出处,如有侵权 一经发现 必将追究其法律责任

18 0
收藏该文
已收藏

评论内容：(最多支持255个字符)




程序员的那些事(new) 更多>

2022年最受欢迎的8大编程语言

为什么都说程序员找不到女朋友，但是身边程序猿的却没一个单身的

30岁以上你还死磕技术，别说拿高薪，可能你连饭碗都会保不住

程序员被开除，老板：“有你参与的项目全黄了！”

笑话：一个测试工程师走进一家酒吧

趣图：程序员头疼的4种原因

笑话：面试官：请拿出一段体现你水平的代码。我： sudo rm -rf /*面试官：这体现了你哪方面能力？

java精选：SSO单点登录】JWT入门概述&&残留的安全问题

网友说：做开发，不被领导喜欢怎么办？

网友说：我奉劝各位，一定不能在职场透露自己的家庭条件

电子书(new)

java jdk8 学习笔记

深入剖析Tomcat pdf下载

Java与模式 pdf下载

深入理解Java虚拟机：JVM高级特性与最佳实践(第2版) pdf 下载

数据结构与算法分析：Java语言描述(原书第3版) pdf  下载

Java并发编程实战 中文版 PDF扫描版[9MB]

数据结构与算法分析：Java语言描述(原书第3版) 中文完整pdf扫描版[47MB] 附源码

Hadoop权威指南 pdf下载

重构 改善既有代码的设计 pdf下载

JAVA编程思想 pdf下载

脚本(new)

输入一个数据n，计算斐波那契数列(Fibonacci)的第n个值

求 a+aa+aaa+.......+aaaaaaaaa=?

输出所有的水仙花数，把谓水仙花数是指一个数3位数，其各各位数字立方和等于其本身，

利用for循环打印 9*9 表?

编写程序求 1+3+5+7+……+99 的和值。

给定一个百分制的分数，输出相应的等级

编写程序，判断给定的某个年份是否是闰年

一些有趣的java小程序

菱形的图形生成器，2到100以内的质数-java实用小程序

java代码游戏编写

博客(new)

Android Studio App开发实战项目之广告轮播（附源码 可用于大作业）

【Java 基础】Java SPI 二 之 Java APT原理及APT实战 - 一步步教你写ButterKnife

Android程序设计之音乐播放器实现

原力计划

学生管理系统（Java实现）

书评 | 《深入理解高并发编程：JDK核心技术》

springboot整合sharding-jdbc实现分库分表详解

【熬夜送书 | 第三期】清华社赞助 | 《Java系列丛书》

Spring Security 6 配置方法，废弃 WebSecurityConfigurerAdapter

原力计划

视频教程(new)

由浅入深，全面解析ThreadLocal

超全面讲解Spring Cloud Alibaba技术栈，java视频教程下载

三天全面系统学习ZooKeeper

2020年JavaSE强化系列教程泛型全剖析，java视频教程下载

详讲编码与解码，灵活解决乱码难题，java 视频教程下载

2020年抗疫之作java基础进阶13天

系统学习让你轻松定义java类加载器-java视频教程下载

真小白福音，完全从0带你掌握计算机与编程基础

java零基础入门到精通（2019版）

2020JAVA基础-深入系统的学习数据结构与算法

项目实战(new)

JSP+SSM+Mysql实现的学生成绩管理系统

JSP+Structs+JDBC+mysql实现的诚欣电子商城

JSP+SSH+Mysql+DBCP实现的租车系统

博客系统java项目

这是一个在线考试系统,java项目实战源码下载

简单状态机

Java Web编程课程中开发的项目

银行账户项目样本 用Java完成的一个简单项目

一个使用Java开发在线概述用户管理平台

JAVAWeb项目 JAVA-WEB开发的一些练手项目，这些也适合初学者进行练习

问答(new)

启动一个使用Rapid miner的java项目

如何通过 Apache POI 3.9 从 xls/xlsx 读取时间格式？

如何将自定义菜单栏项放置在地图菜单中的所需位置

我们如何在 Jess 规则中从终端选择默认值

无法在远程系统上使用 Windows 身份验证连接到 MS sql 服务器

Spring - 如何选择依赖bean的属性？

Java - MousePress Hold 和 Release 事件侦听器

将分页与 Struts 2 和 Hibernate 一起使用

Java：运动，需要放慢速度

如何正确调用同一个类中的方法内的方法？

游戏(new)

2人对战游戏，java游戏

java小游戏-数学英雄

java游戏-蛙人

经典骰子游戏,java游戏源码下载

一些java小游戏

java小游戏-抓住这只球

二十一点，java小游戏源码下载

java小游戏集合下载

java五子棋游戏源码下载

java贪吃蛇游戏

其他资源(new)

某公司的雇员分为以下若干类： Employee：这是所有员工总的父类，属性：员工的姓名和生日月份。 方法：getSalary(int month) 根据参数月份来确定工资，如果该月员工过生日，

判断随机整数是否是素数 产生100个0-999之间的随机整数，然后判断这100个随机整数哪些是素数，哪些不是？

完成九宫格程序

. 定义一个int型的一维数组，包含10个元素，分别赋一些随机整数，然后求出所有元素的最大值

歌德巴赫猜想,任何一个大于六的偶数可以拆分成两个质数的和

在屏幕上打印出n行的金字塔图案，如，若n=5,则图案如下

计算圆周率

利用程序输出如下图形:

求 2/1+3/2+5/3+8/5+13/8.....前20项之和？

Nutch入门教程 pdf下载