【Java数据结构】二叉树进阶——非递归实现前中后序遍历二叉树(深入理解二叉树)+进阶大厂面试题(一行一注释)

【Java数据结构】二叉树进阶——非递归实现前中后序遍历二叉树(深入理解二叉树)+进阶大厂面试题(一行一注释)

【Java数据结构】二叉树进阶——非递归实现前中后序遍历二叉树+进阶大厂面试题

????非递归实现遍历二叉树(深入理解二叉树)

⭐非递归前序遍历

⭐非递归中序遍历

⭐非递归后序遍历

????大厂OJ面试题

????1. 二叉树的构建及遍历

????2. 二叉树的分层遍历

????3. 给定一个二叉树,找到该树中两个指定节点的最近公共祖先

????4. 二叉树搜索树转换成排序双向链表

????5. 根据一棵树的前序遍历与中序遍历构造二叉树

????6. 根据一棵树的中序遍历和后序遍历构造二叉树

????7. 二叉树创建字符串

????非递归实现遍历二叉树(深入理解二叉树)

代码每行都有注释,可以一步一步的画着图走一走,多走几遍,理解会上一个档次!

前序遍历和中序遍历都用到栈,代码可以说一模一样,只不过打印节点的时机不一样

⭐非递归前序遍历

【Java数据结构】二叉树进阶——非递归实现前中后序遍历二叉树(深入理解二叉树)+进阶大厂面试题(一行一注释)

⭐非递归中序遍历

【Java数据结构】二叉树进阶——非递归实现前中后序遍历二叉树(深入理解二叉树)+进阶大厂面试题(一行一注释)

⭐非递归后序遍历

【Java数据结构】二叉树进阶——非递归实现前中后序遍历二叉树(深入理解二叉树)+进阶大厂面试题(一行一注释)

????大厂OJ面试题

????1. 二叉树的构建及遍历

题目:

【Java数据结构】二叉树进阶——非递归实现前中后序遍历二叉树(深入理解二叉树)+进阶大厂面试题(一行一注释)

思路:

  1. 本题思路很简单,就是遍历字符串,因为这是根据前序遍历搞出来的字符串
  2. 所以构建二叉树,也要根据这个 根->左节点->右节点 的顺序来构建

【Java数据结构】二叉树进阶——非递归实现前中后序遍历二叉树(深入理解二叉树)+进阶大厂面试题(一行一注释)

实现代码:

import java.util.*;
//题目啥也没给,节点类也要自己定义一下
class TreeNode{
    char value;//节点有值
    TreeNode left;//有左孩子节点
    TreeNode right;//有右孩子节点
    public TreeNode(char value){//构造函数,用于给节点赋值
        this.value = value;
    }
}

public class Main{
 //主函数,用于输入字符串,主要在creatTree方法里来实现
 public static void main(String[]args){
        Scanner scn = new Scanner(System.in);
        String str = scn.nextLine();
        TreeNode root =  creatTree(str);
        inOrderTraveled(root);
    }

  
    public static int i = 0;//i用于记录字符串中字符的下标
    //因为构建过程是递归的,不能用局部变量,所以要在外部设置成静态的
    public static TreeNode creatTree(String str){
        if(str==null){//如果字符串为空
            return null;//直接返回null
        }
        //字符串不为空,就进行构构建二叉树的过程
        TreeNode root = null;//先创建一个根节点,指向空,这样做是为了初始化
        if(str.charAt(i)!='#'){//依次读取字符串中的字符,不为 # 就进行二叉树构造
            root = new TreeNode(str.charAt(i));//将读取的字符给节点实例化
            i++;//当前读取的字符被用过之后,字符串下标要往后走一位
            root.left = creatTree(str);//递归构建左树
            root.right = creatTree(str);//递归构建右树
        }else{//读取到的字符是 # ,代表空节点,不用构建
            i++;//字符串下标往后走一位
        }
        return root;//最后返回根节点即可
    }
    
    //对构建好的二叉树进行中序遍历,用递归实现就好了
    public static void inOrderTraveled(TreeNode root){
        if(root==null) return;
        inOrderTraveled(root.left);
        System.out.print(root.value+" ");
        inOrderTraveled(root.right);
    }
}


????2. 二叉树的分层遍历

题目:

【Java数据结构】二叉树进阶——非递归实现前中后序遍历二叉树(深入理解二叉树)+进阶大厂面试题(一行一注释)

思路:

  1. 层序遍历就是一层一层的遍历节点

【Java数据结构】二叉树进阶——非递归实现前中后序遍历二叉树(深入理解二叉树)+进阶大厂面试题(一行一注释)

这题还有一个要求就是,输出的时候将一层的节点放在一行,下一层的节点放在下一行,这就需要用到一个二维数组来储存每一层的节点

【Java数据结构】二叉树进阶——非递归实现前中后序遍历二叉树(深入理解二叉树)+进阶大厂面试题(一行一注释)

我们先来观察一下 层序遍历的过程中,结点进队列和出队列的过程: 请看图

【Java数据结构】二叉树进阶——非递归实现前中后序遍历二叉树(深入理解二叉树)+进阶大厂面试题(一行一注释)

可是如何知道当前访问到的节点是哪一层的呢? 截取 BFS 遍历过程中的某个时刻:

【Java数据结构】二叉树进阶——非递归实现前中后序遍历二叉树(深入理解二叉树)+进阶大厂面试题(一行一注释)

可以看到,此时队列中的结点是 3、4、5,分别来自第 1 层和第 2 层。这个时候,第 1 层的结点还没出完,第 2 层的结点就进来了,而且两层的结点在队列中紧挨在一起,我们无法区分队列中的结点来自哪一层。

因此,我们在每一层遍历开始前,先记录队列中的结点数量 n(也就是这一层的结点数量),然后一口气处理完这一层的 n 个结点

【Java数据结构】二叉树进阶——非递归实现前中后序遍历二叉树(深入理解二叉树)+进阶大厂面试题(一行一注释)

实现代码:

【Java数据结构】二叉树进阶——非递归实现前中后序遍历二叉树(深入理解二叉树)+进阶大厂面试题(一行一注释)

????3. 给定一个二叉树,找到该树中两个指定节点的最近公共祖先

题目:

【Java数据结构】二叉树进阶——非递归实现前中后序遍历二叉树(深入理解二叉树)+进阶大厂面试题(一行一注释)

思路:


祖先的定义: 若节点 p 在节点 root 的左(右)子树中,或 p = root ,则称 root 是 p 的祖先。


根据以上定义,若 root 是 p,q 的 最近公共祖先 ,则只可能为以下情况之一:

①p 和 q 在 root的子树中,且分列 root 的 异侧(即分别在左、右子树中);

②p = root ,且 q 在 root 的左或右子树中;

③q = root ,且 p 在 root 的左或右子树中;

【Java数据结构】二叉树进阶——非递归实现前中后序遍历二叉树(深入理解二叉树)+进阶大厂面试题(一行一注释)

考虑通过递归对二叉树进行先序遍历,当遇到节点 p 或 q 时返回。从底至顶回溯,当节点 p,q 在节点 root的异侧时,节点 root 即为最近公共祖先,则向上返回 root 。

【Java数据结构】二叉树进阶——非递归实现前中后序遍历二叉树(深入理解二叉树)+进阶大厂面试题(一行一注释)

实现代码:

【Java数据结构】二叉树进阶——非递归实现前中后序遍历二叉树(深入理解二叉树)+进阶大厂面试题(一行一注释)

????4. 二叉树搜索树转换成排序双向链表

题目:

【Java数据结构】二叉树进阶——非递归实现前中后序遍历二叉树(深入理解二叉树)+进阶大厂面试题(一行一注释)

思路:

  1. 已知将二叉搜索树进行中序遍历可以得到由小到大的顺序排列,因此本题最直接的想法就是进行中序遍历
  2. 根据题目的要求1,不能创建新的结点,所以我们设置一个pre用于指向前驱节点

【Java数据结构】二叉树进阶——非递归实现前中后序遍历二叉树(深入理解二叉树)+进阶大厂面试题(一行一注释)

实现代码:

【Java数据结构】二叉树进阶——非递归实现前中后序遍历二叉树(深入理解二叉树)+进阶大厂面试题(一行一注释)

????5. 根据一棵树的前序遍历与中序遍历构造二叉树

题目:

【Java数据结构】二叉树进阶——非递归实现前中后序遍历二叉树(深入理解二叉树)+进阶大厂面试题(一行一注释)

思路:

  1. 所以我们只需要根据先序遍历得到根节点,然后在中序遍历中找到根节点的位置,它的左边就是左子树的节点,右边就是右子树的节点。

【Java数据结构】二叉树进阶——非递归实现前中后序遍历二叉树(深入理解二叉树)+进阶大厂面试题(一行一注释)

递归生成左子树和右子树

【Java数据结构】二叉树进阶——非递归实现前中后序遍历二叉树(深入理解二叉树)+进阶大厂面试题(一行一注释)

实现代码:

【Java数据结构】二叉树进阶——非递归实现前中后序遍历二叉树(深入理解二叉树)+进阶大厂面试题(一行一注释)

????6. 根据一棵树的中序遍历和后序遍历构造二叉树

题目:

【Java数据结构】二叉树进阶——非递归实现前中后序遍历二叉树(深入理解二叉树)+进阶大厂面试题(一行一注释)

思路:

  1. 和上题几乎一样,只需要几处小改动
  2. 因为是给的是后续遍历,所以构建的时候,读取后续遍历数组要从后往前读取 ,并且构建的时候是 根->右->左

实现代码:

【Java数据结构】二叉树进阶——非递归实现前中后序遍历二叉树(深入理解二叉树)+进阶大厂面试题(一行一注释)


????7. 二叉树创建字符串

题目:

【Java数据结构】二叉树进阶——非递归实现前中后序遍历二叉树(深入理解二叉树)+进阶大厂面试题(一行一注释)

思路:

  1. 我们可以使用递归的方法得到二叉树的前序遍历。在递归时,根据题目描述,我们需要加上额外的括号,会有以下 4 种情况:
    ① 如果当前节点有两个孩子,那我们在递归时,需要在两个孩子的结果外都加上一层括号;
    ②如果当前节点没有孩子,那我们不需要在节点后面加上任何括号
  2. 【Java数据结构】二叉树进阶——非递归实现前中后序遍历二叉树(深入理解二叉树)+进阶大厂面试题(一行一注释)
  3. 如果当前节点只有左孩子,那我们在递归时,只需要在左孩子的结果外加上一层括号,而不需要给右孩子加上任何括号

【Java数据结构】二叉树进阶——非递归实现前中后序遍历二叉树(深入理解二叉树)+进阶大厂面试题(一行一注释)

④如果当前节点只有右孩子,那我们在递归时,需要先加上一层空的括号 () 表示左孩子为空,再对右孩子进行递归,并在结果外加上

【Java数据结构】二叉树进阶——非递归实现前中后序遍历二叉树(深入理解二叉树)+进阶大厂面试题(一行一注释)

考虑完上面的 4 种情况,我们就可以得到最终的字符串。

实现代码:

【Java数据结构】二叉树进阶——非递归实现前中后序遍历二叉树(深入理解二叉树)+进阶大厂面试题(一行一注释)









上一篇:SQL Server Case when 的使用方法总结


下一篇:【Java】认识异常及自定义异常