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

[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
  • 节点的层次:从根开始定义,根为第一层,根的子节点为第二层,以此类推.
  • 树的深度:树的最大层次.如上图树的深度为3.

2.树的应用

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


二>二叉树

1.二叉树的概念

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

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

 2.两种特殊的二叉树

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

3.二叉树的性质

  • 若规定根节点的层数为1,则一颗非空二叉树的第i层有有 2^{i-1}(i>0)个节点.
  • 若规定根节点的二叉树的深度为1,则深度为k的二叉树的最大节点个数为2^{k-1}(k>=0).
  • 对于高度为k的二叉树,最多有2^{k+1}-1个节点.
  • 对任何一颗二叉树,如果其叶子节点个数为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.二叉树的存储

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

class Node {
int val; // 数据域
Node left; // 左孩子的引用,常常代表左孩子为根的整棵左子树
Node right; // 右孩子的引用,常常代表右孩子为根的整棵右子树
}

5.二叉树的创建

二叉树的创建需要三步:

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

class TreeNode{//二叉树节点
   int data;
   TreeNode1 leftChild;
   TreeNode1 rightChild;

    public TreeNode1(int data) {
        this.data = data;
    }
}
public static TreeNode createBinaryTree(LinkedList<Integer> inputList){//创建二叉树
        TreeNode node = null;
        if (inputList==null||inputList.isEmpty()){
            return null;
        }
        Integer data = inputList.removeFirst();//每次取出集合中的第一个元素
        //这里判空很重要,如果元素为空,则不在进一步递归.
        if (data!=null){
            node = new TreeNode1(data);
            node.leftChild = createBinaryTree(inputList);
            node.rightChild = createBinaryTree(inputList);
        }
        return node;
    }
public static void main(String[] args) {
        LinkedList<Integer> inputList = new LinkedList<>        
        (Arrays.asList(3,2,9,null,null,10,null,null,8,null,4));
        TreeNode1 treeNode1 = createBinaryTree(inputList);
    }

6.二叉树的遍历

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

1)前序遍历

public static void preOrderTraveral(TreeNode node){//to前序遍历
        if (node==null){
            return;
        }
        System.out.print(node.data+" ");
        preOrderTraveral(node.leftChild);
        preOrderTraveral(node.rightChild);
    }

2)中序遍历

public static void midOrderTraveral(TreeNode node){//中序遍历
        if (node==null){
            return;
        }
        midOrderTraveral(node.leftChild);
        System.out.print(node.data+" ");
        midOrderTraveral(node.rightChild);
    }

3)后序遍历 

public static void lastOrderTraveral(TreeNode node){//后序遍历
        if (node==null){
            return;
        }
        lastOrderTraveral(node.leftChild);
        lastOrderTraveral(node.rightChild);
        System.out.print(node.data+" ");
    }

4)层序遍历

  public static void levelOrderTraveral(TreeNode root) {//层序遍历
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        while (!queue.isEmpty()){
            TreeNode node = queue.poll();
            System.out.println(node.data);
            if (node.leftChild!=null){
                queue.offer(node.leftChild);
            }
            if (node.rightChild!=null){
                queue.offer((node.rightChild));
            }
        }
    }

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

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

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

class Solution {//遍历思路
    int count = 0;
    public int countNodes(TreeNode root) {
        if(root==null){
            return 0;
        }
            count++;
            countNodes(root.left);
            countNodes(root.right);
    return count;
  }
}
class Solution {//子问题思路拆解写法
    public int countNodes(TreeNode root) {
        if(root==null){
            return 0;
        }
        int leftTreeCount = countNodes(root.left);
        int rightTreeCount = countNodes(root.right);
        return leftTreeCount+rightTreeCount+1;
    }
}

6)leetcode提交做法

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

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

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

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

public List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> ret = new ArrayList();
        if(root==null) return ret;
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        while(!queue.isEmpty()){
            int size = queue.size();
            List<Integer> list = new ArrayList<>();
            while(size!=0){
                TreeNode cur = queue.poll();
                if(cur.left!=null){
                    queue.offer(cur.left);
                }
                if(cur.right!=null){
                    queue.offer(cur.right);
                }
                size--;
                list.add(cur.val);
            }
            ret.add(list);
        }
        return ret;

    }

三 >二叉树常见面试题

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.节点个数

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

class Solution {//子问题思路
    public int countNodes(TreeNode root) {
        if(root==null){
            return 0;
        }
        return countNodes(root.left)+countNodes(root.right)+1;
    }
}
class Solution {//子问题思路拆解写法
    public int countNodes(TreeNode root) {
        if(root==null){
            return 0;
        }
        int leftTreeCount = countNodes(root.left);
        int rightTreeCount = countNodes(root.right);
        return leftTreeCount+rightTreeCount+1;
    }
}
class Solution {//遍历思路
    int count = 0;
    public int countNodes(TreeNode root) {
        if(root==null){
            return 0;
        }
            count++;
            countNodes(root.left);
            countNodes(root.right);
    return count;
  }
}

2.叶子节点个数

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

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

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

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

 

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

4.二叉树的高度

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

 

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

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

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

public static TreeNode find(TreeNode root,char val){//检测value元素是否存在
        if (root==null){
            return null;
        }
        if (root.data==val){
            return root;
        }
        TreeNode retLeft = find(root.leftChild,val);//先去左树找
        if (retLeft!=null){//说明找到了
            return retLeft;
        }
        TreeNode retRight = find(root.rightChild,val);//再去右树找
        if (retRight!=null){//说明找到了
            return retRight;
        }
        return null;
    }

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

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

 public static boolean isCompleteTree1(TreeNode root){//判断是不是完全二叉树,队列
        if (root==null)return true;
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        while (!queue.isEmpty()){
            TreeNode cur = queue.poll();
            if (cur!=null){
                queue.offer(cur.leftChild);
                queue.offer(cur.rightChild);
            }else {
                break;
            }
        }
        while (!queue.isEmpty()){
            if (queue.poll()!=null){
                return false;
            }
        }
        return true;
    }

7.相同的树

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

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

public boolean isSameTree(TreeNode p, TreeNode q) {
        if(p==null&&q!=null)return false;
        if(p!=null&&q==null)return false;
        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);
    }

8.另一棵树的子树

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

 时间复杂度O(m*n)

本质判断相同

public boolean isSameTree(TreeNode p, TreeNode q) {
        if(p==null&&q!=null)return false;
        if(p!=null&&q==null)return false;
        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);
    }
    public boolean isSubtree(TreeNode root, TreeNode subRoot) {
        if(root==null||subRoot==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;
    }

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

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

时间复杂度O(N^2)

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

public int height (TreeNode root){
        if(root==null){
            return 0;
        }
        int leftHeight = height(root.left);
        int rightHeight = height(root.right);
        return leftHeight>rightHeight?(leftHeight+1):(rightHeight+1);
    }
    public boolean isBalanced(TreeNode root) {
        if(root==null){
            return true;
        }
        int leftHeight = height(root.left);
        int rightHeight = height(root.right);
        return Math.abs(leftHeight-rightHeight)<=1&&isBalanced(root.left)&&isBalanced(root.right);

    }

时间复杂度O(N)

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

public int height (TreeNode root){
        if(root==null){
            return 0;
        }
        int leftHeight = height(root.left);
        int rightHeight = height(root.right);
        if(leftHeight>=0&&rightHeight>=0&&Math.abs(leftHeight-rightHeight)<=1){
           return leftHeight>rightHeight?(leftHeight+1):(rightHeight+1);
        }else{
            return -1;
        }
    }
    public boolean isBalanced(TreeNode root) {
        if(root==null){
            return true;
        }
       return height(root)>=0;
    }

10.对称二叉树

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

public boolean isSymmetricChild(TreeNode rootleft,TreeNode rootrigth){
        
        if(rootleft==null&&rootrigth!=null){
            return false;
        }
        if(rootleft!=null&&rootrigth==null){
            return false;
        }
        if(rootleft==null&&rootrigth==null){
            return true;
        }
        if(rootleft.val!=rootrigth.val){
            return false;
        }
        return isSymmetricChild(rootleft.left,rootrigth.right)&&isSymmetricChild(rootleft.right,rootrigth.left);
    }
    public boolean isSymmetric(TreeNode root) {
        if(root==null){
            return true;
        }
        return isSymmetricChild(root.left,root.right);
    }

11.创建二叉树

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

import java.util.*;

class TreeNode{//创建结点
    public char val;
    public TreeNode left;
    public TreeNode right;
    public TreeNode(char val){
        this.val = val;
    }
}
public class Main{
    public static int i = 0;
    public static TreeNode createTree(String str){//创建二叉树
        TreeNode root = null;
        if(str.charAt(i)!='#'){
            root = new TreeNode(str.charAt(i));
            i++;
            root.left = createTree(str);
            root.right = createTree(str);
        }else{
            i++;
        }
        return root;
    }
    public static void inorder(TreeNode root){//中序遍历
        if(root==null){
            return ;
        }
        inorder(root.left);
        System.out.print(root.val+" ");
        inorder(root.right);
    }
    public static void main(String[] args){
        Scanner in = new Scanner(System.in);
        while(in.hasNextLine()){
            String str = in.nextLine();
            TreeNode root = createTree(str);
            inorder(root);
        }
    }
}

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

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

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

public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if(root==null) return null;
        if(root==p||root==q){
            return root;
        }
        TreeNode leftT = lowestCommonAncestor(root.left,p,q);
        TreeNode rightT = lowestCommonAncestor(root.right,p,q);
        if(leftT!=null&&rightT!=null){
            return root;
        }else if(leftT!=null){
            return leftT;
        }else{
            return rightT;
        }
    }

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

public 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 flg = getPath(root.left,node,stack);
        if(flg==true){
            return true;
        }
        flg = getPath(root.right,node,stack);
        if(flg==true){
            return true;
        }
        stack.pop();
        return false;
    }
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if(root==null) return null;
        Stack<TreeNode> stack1 = new Stack<>();
        getPath(root,p,stack1);
        Stack<TreeNode> stack2 = new Stack<>();
        getPath(root,q,stack2);

        int size1 = stack1.size();
        int size2 = stack2.size();
        if(size1>size2){
            int size = size1-size2;
            while(size!=0){
                stack1.pop();
                size--;
            }
            while(!stack1.isEmpty()&&!stack2.isEmpty()){
                if(stack1.peek()==stack2.peek()){
                    return stack1.pop();
                }else{
                    stack1.pop();
                    stack2.pop();
                }
            }
        }else{
            int size = size2-size1;
            while(size!=0){
                stack2.pop();
                size--;
            }
            while(!stack1.isEmpty()&&!stack2.isEmpty()){
                if(stack1.peek()==stack2.peek()){
                    return stack2.pop();
                }else{
                    stack1.pop();
                    stack2.pop();
                }
            }
        }
        return null;
    }

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

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

TreeNode prev = null;
    public void inOrder(TreeNode node){
        if(node==null) return;
        inOrder(node.left);
        //打印
        node.left = prev;
        if(prev!=null){
            prev.right = node;
        }
        prev = node;
        inOrder(node.right);
    }
    public TreeNode Convert(TreeNode pRootOfTree) {
        if(pRootOfTree==null) return null;
        inOrder(pRootOfTree);
        TreeNode head = pRootOfTree;
        while(head.left!=null){
            head = head.left;
        }
        return head;
    }

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

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

int preIndex = 0;
    public TreeNode creativePbyI(int[] preorder, int[] inorder,int beging,int end){
        if(beging>end){
            return null;
        }
        TreeNode root = new TreeNode(preorder[preIndex]);
        int rootIndex = findIndex(inorder,beging,end,preorder[preIndex]);
        if(rootIndex==-1){
            return null;
        }
        preIndex++;
        root.left = creativePbyI(preorder,inorder,beging,rootIndex-1);
        root.right = creativePbyI(preorder,inorder,rootIndex+1,end);
        return root;
    }
    public int findIndex( int[] inorder,int beging,int end,int key){
        for(int i = 0;i<=end;i++){
            if(inorder[i]==key){
                return i;
            }
        }
        return -1;
    }
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        if(preorder==null||inorder==null){
            return null;
        }
        return creativePbyI(preorder,inorder,0,preorder.length-1);
    }

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

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

int postIndex = 0;
    public TreeNode creativePbyI(int[] inorder, int[] postorder,int beging,int end){
        if(beging>end){
            return null;
        }
        TreeNode root = new TreeNode(postorder[postIndex]);
        int rootIndex = findIndex(inorder,beging,end,postorder[postIndex]);
        if(rootIndex==-1){
            return null;
        }
        postIndex--;
        root.right = creativePbyI(inorder,postorder,rootIndex+1,end);
        root.left = creativePbyI(inorder,postorder,beging,rootIndex-1);
        return root;
    }
    public int findIndex( int[] inorder,int beging,int end,int key){
        for(int i = 0;i<=end;i++){
            if(inorder[i]==key){
                return i;
            }
        }
        return -1;
    }
    
    public TreeNode buildTree(int[] inorder, int[] postorder) {
        if(postorder==null||inorder==null){
            return null;
        }
        postIndex = postorder.length-1;
        return creativePbyI(inorder,postorder,0,inorder.length-1);
    }

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

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

public void treeToString(TreeNode t,StringBuffer sb){
        if(t==null){
            return;
        }
        sb.append(t.val);
        if(t.left!=null){
            sb.append("(");
            treeToString(t.left,sb);
            sb.append(")");
        }else{
            //t.left==null
            if(t.right==null){
                return;
            }else{
                sb.append("()");
            }
        }
        if(t.right!=null){
            sb.append("(");
            treeToString(t.right,sb);
            sb.append(")");
        }else{
            return;
        }

    }
    public String tree2str(TreeNode root) {
        if(root==null) return null;
        StringBuffer sb = new StringBuffer();
        treeToString(root,sb);
        return sb.toString();
    }

17.前序遍历非递归写法

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

public static void preOrderTraveralWithStack(TreeNode root){//非递归前序遍历
        Stack<TreeNode> stack = new Stack<TreeNode>();
        TreeNode node = root;
        while (node!=null||!stack.isEmpty()){
            while (node!=null){
                System.out.println(node.data);
                stack.push(node);
                node = node.leftChild;
            }
            if(!stack.isEmpty()){
                node = stack.pop();
                node = node.rightChild;
            }
        }
    }

18.中序遍历非递归写法

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

 public List<Integer>inorderTraversal(TreeNode root) {
        List<Integer> ret = new ArrayList<>();
        if(root==null) return ret;
        Stack<TreeNode> stack = new Stack<>();
        TreeNode cur = root;
        while(cur!=null||!stack.isEmpty()){
            while(cur!=null){
            stack.push(cur);
            cur = cur.left;
        }
        if(!stack.isEmpty()){
            TreeNode top = stack.pop();
            ret.add(top.val);
            cur = top.right;
        }
    }
    return ret;
  }

19.后序遍历非递归写法

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

public List<Integer> postorderTraversal(TreeNode root) {
        List<Integer> ret = new ArrayList<>();
        if(root==null) return ret;
        Stack<TreeNode> stack = new Stack<>();
        TreeNode cur = root;
        TreeNode prev = null;
        while(cur!=null||!stack.isEmpty()){
            while(cur!=null){
            stack.push(cur);
            cur = cur.left;
        }
        TreeNode top = stack.peek();
        if(top.right==null||top.right==prev){
            stack.pop();
            ret.add(top.val);
            prev = top;//记录最近一次遍历二叉树
        }else{
            cur = top.right;
        }
    }
    return ret;
   }

总结>

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

相关文章:

  • 输出UE当前所有UObject的基础信息
  • 【MicroPython ESP32】1.8“tft ST7735带中文驱动显示示例
  • QT提取数据库内容,根据不同字段要求显示不同颜色
  • 最简便的工厂模式
  • 【实战项目】高并发内存池(模拟实现mini_tcmalloc)
  • 173.CI/CD(一):gitlab配置,jenkins的安装配置,jenkins实现基础的CI/CD,Sonarqube代码质量检测,Harbor镜像仓库
  • FastAPI 学习之路(二十七)安全校验
  • office32位和64位有什么区别
  • 猿创征文|python求解四位数 青少年编程电子学会python编程等级考试三级真题解析2021年03月
  • 当事人胜诉后,所预交受理费是否应予退还
  • uniapp的拨打电话,下拉和上划
  • 如何确定 RMAN 的多路复用级别
  • Java excel poi 读取已有文件 ,动态插入一列数据
  • Java项目:SSM企业工资管理系统
  • Python基于Django的汽车销售网站
  • [PHP内核探索]PHP中的哈希表
  • 2018一半小结一波
  • 30秒的PHP代码片段(1)数组 - Array
  • Js基础知识(一) - 变量
  • leetcode46 Permutation 排列组合
  • node-sass 安装卡在 node scripts/install.js 解决办法
  • Otto开发初探——微服务依赖管理新利器
  • React 快速上手 - 07 前端路由 react-router
  • Vue学习第二天
  • 从PHP迁移至Golang - 基础篇
  • 大整数乘法-表格法
  • 入门到放弃node系列之Hello Word篇
  • 深度解析利用ES6进行Promise封装总结
  • 云大使推广中的常见热门问题
  • k8s使用glusterfs实现动态持久化存储
  • ​LeetCode解法汇总2670. 找出不同元素数目差数组
  • !!Dom4j 学习笔记
  • #pragma 指令
  • $.ajax()
  • (1)SpringCloud 整合Python
  • (6)STL算法之转换
  • (C)一些题4
  • (二)fiber的基本认识
  • (转)我也是一只IT小小鸟
  • (轉貼) 寄發紅帖基本原則(教育部禮儀司頒布) (雜項)
  • *ST京蓝入股力合节能 着力绿色智慧城市服务
  • .Net CF下精确的计时器
  • .NET Compact Framework 多线程环境下的UI异步刷新
  • .net core webapi 大文件上传到wwwroot文件夹
  • .net 受管制代码
  • .NET值类型变量“活”在哪?
  • .ui文件相关
  • @transactional 方法执行完再commit_当@Transactional遇到@CacheEvict,你的代码是不是有bug!...
  • [ web基础篇 ] Burp Suite 爆破 Basic 认证密码
  • [ 云计算 | AWS ] AI 编程助手新势力 Amazon CodeWhisperer:优势功能及实用技巧
  • [28期] lamp兄弟连28期学员手册,请大家务必看一下
  • [8-23]知识梳理:文件系统、Bash基础特性、目录管理、文件管理、文本查看编辑处理...
  • [AI]文心一言爆火的同时,ChatGPT带来了这么多的开源项目你了解吗
  • [Angularjs]asp.net mvc+angularjs+web api单页应用
  • [ASP.NET MVC]如何定制Numeric属性/字段验证消息