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

    专栏简介 :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+12i+1,否则无左孩子.
      • 若2i+22i+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}" role="presentation" style="position: relative;">{\color{Red} \frac{1-2^{n}}{1-2}   .那么节点数为n的深度为log2n+1" role="presentation" style="position: relative;">log2n+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 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 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 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 relist = new ArrayList();//集合创建在类外
    2.     public List 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 preorderTraversal(TreeNode root) {//子问题思路
    2.         List relist = new ArrayList();
    3.         if(root==null){
    4.             return relist;
    5.         }
    6.         relist.add(root.val);
    7.         List leftTree = preorderTraversal(root.left);
    8.         relist.addAll(leftTree);//所有的左树
    9.         List rigthTree = preorderTraversal(root.right);
    10.         relist.addAll(rigthTree);//所有的右树
    11.         return relist;
    12.     }

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

    • Tips:当前队列中元素的个数,决定下一层需要入队几个元素.(例如:如果队列中有两个节点,那么正常情况下,下一层必定有4个节点.而一次最多入队2个节点,所以我们需要循环两次)

    1. public List> levelOrder(TreeNode root) {
    2.         List> ret = new ArrayList();
    3.         if(root==null) return ret;
    4.         Queue queue = new LinkedList<>();
    5.         queue.offer(root);
    6.         while(!queue.isEmpty()){
    7.             int size = queue.size();
    8.             List 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度节点就对应200个0度节点.(A)

    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 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,Stackstack){
    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 stack1 = new Stack<>();
    23.         getPath(root,p,stack1);
    24.         Stack 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 stack = new Stack();
    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 ListinorderTraversal(TreeNode root) {
    2.         List ret = new ArrayList<>();
    3.         if(root==null) return ret;
    4.         Stack 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 postorderTraversal(TreeNode root) {
    2.         List ret = new ArrayList<>();
    3.         if(root==null) return ret;
    4.         Stack 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.    }

    总结>

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

  • 相关阅读:
    Java对象的分配和内存布局
    loss&BN
    java ssm Vue客户关系管理系统springboot
    TP5 中 FIND_IN_SET的使用方法 精准匹配，字段值以“,”隔开查询
    LM2904DT运算放大器中文资料规格书PDF数据手册引脚图参数图片功能概述
    基于安卓android微信小程序的食谱大全系统
    【Miniconda】Linux系统中 .condarc 配置文件的位置一般在哪里
    挑战10个最难的Java面试题（附答案）【上】
    【JVM】jvm的体系结构
    设计一个高效算法，将顺序表L的所有元素逆置，要求算法的空间复杂度为O（1）
  • 原文地址：https://blog.csdn.net/liu_xuixui/article/details/126138054