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

简介: 笔记

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


题目:

1.png思路:


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


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

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

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

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


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

3.png

实现代码:

class Solution {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if(root==null)  return null;//根节点空的话,直接返回null,无公共祖先
        if(root==p || root == q)  return root;//如果q或者p就是根节点,那直接返回,此时他们就是最近公共祖先
        //一开始的根节点不是祖先就往下遍历左右子树
        //递归左树找目标点q和p,找到的话会返回找到的节点,没找到则返回空
        TreeNode leftTree = lowestCommonAncestor(root.left,p,q);
        //递归右树找目标点q和p,找到的话会返回找到的节点,没找到则返回空
        TreeNode rightTree = lowestCommonAncestor(root.right,p,q);
        //如果两边都找到了目标点(q/p)那么当前这个节点就是最近祖先
        if(leftTree!=null && rightTree!=null){
            return root;
        }
        //代码走到这里说明有一个为空(没找到目标点)
        //只有左边找到了目标点(q/p),那当前根节点的左节点就是最近祖先
        if(leftTree!=null){
            return leftTree;
        }
        //只有右边找到了目标点(q/p),那当前根节点的右节点就是最近祖先
        if(rightTree!=null){
            return rightTree;
        }
        //没有找到目标点q或者p
        return null;
    }
}


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


题目:

6.png


思路:

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



  1. 例如root为指向10的时候,preNode指向8,如图所示:7.png

实现代码:

public class Solution {
    public TreeNode pre = null;//因为是要递归,所以pre要设在外部
    public void ConvertChild(TreeNode pcur) {
        if(pcur==null){
            return;
        }
        ConvertChild(pcur.left);//因为是中序遍历,所以先递归左节点
        //处理根节点
        //关键点
        pcur.left=pre;//当前节点的左指针指向前驱节点
        if(pre!=null){//如果前驱节点非空
          pre.right=pcur;//前驱节点右指针指向当前节点
        }
        pre=pcur;//pre走到当前节点,也就是当前节点成为下一个节点的前驱节点
        //三行代码,关键点
        ConvertChild(pcur.right);//递归左节点
    }
    public TreeNode Convert(TreeNode pRootOfTree) {
        if(pRootOfTree==null) return null;
        ConvertChild(pRootOfTree);
        TreeNode head = pRootOfTree;
        while(head.left!=null){
            head=head.left;
        }
        return head;
    }
}


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


题目:

9.png

思路:

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

11.gif


实现代码:

class Solution {
    public int preindex = 0;
    public TreeNode buildTreeChild(int[] preorder,int[] inorder,int inbegin,int inend) {
        if(inbegin > inend) {
            return null;//左树 或者 右树 为空
        }
        TreeNode root = new TreeNode(preorder[preindex]);
        //找根节点在中序遍历的数组中的结果
        int rootIndex = findRootIndex(inorder,inbegin,inend,preorder[preindex]);
        preindex++;
        //构建 左树
        root.left = buildTreeChild(preorder,inorder,inbegin,rootIndex-1);
        //构建 右树
        root.right = buildTreeChild(preorder,inorder,rootIndex+1,inend);
        return root;
    }
    //就是一个数组当中的查找代码
    public int findRootIndex(int[] inorder,int inbegin,int inend,int key) {
        for(int i = inbegin;i <= inend;i++) {
            if(inorder[i] == key) {
                return i;
            }
        }
        return -1;
    }
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        if(preorder == null || inorder == null) return null;
        return buildTreeChild(preorder,inorder,0,inorder.length-1);
    }
}


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


题目:

13.png

思路:

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

实现代码:

class Solution {
    public int postindex = 0;
    public TreeNode buildTreeChild(int[] postorder,int[] inorder,int inbegin,int inend) {
        if(inbegin > inend) {
            return null;//左树 或者 右树 为空
        }
        TreeNode root = new TreeNode(postorder[postindex]);
        //找根节点在中序遍历的数组中的结果
        int rootIndex = findRootIndex(inorder,inbegin,inend,postorder[postindex]);
        postindex--;//从后往前
        //构建右树
        root.right = buildTreeChild(postorder,inorder,rootIndex+1,inend);
        //构建左树
        root.left = buildTreeChild(postorder,inorder,inbegin,rootIndex-1);
        return root;
    }
    //就是一个数组当中的查找代码
    public int findRootIndex(int[] inorder,int inbegin,int inend,int key) {
        for(int i = inbegin;i <= inend;i++) {
            if(inorder[i] == key) {
                return i;
            }
        }
        return -1;
    }
    public TreeNode buildTree(int[] inorder, int[] postorder) {
        postindex = postorder.length-1;//将后序遍历数组的下标设为长度-1,即最后一个位置,好让其从后往前遍历数组
        if(postorder == null || inorder == null) return null;
        return buildTreeChild(postorder,inorder,0,inorder.length-1);
    }
}


🎄7. 二叉树创建字符串


题目:

14.png

思路:

  1. 我们可以使用递归的方法得到二叉树的前序遍历。在递归时,根据题目描述,我们需要加上额外的括号,会有以下 4 种情况:
    ① 如果当前节点有两个孩子,那我们在递归时,需要在两个孩子的结果外都加上一层括号;
    ②如果当前节点没有孩子,那我们不需要在节点后面加上任何括号

15.png


③如果当前节点只有左孩子,那我们在递归时,只需要在左孩子的结果外加上一层括号,而不需要给右孩子加上任何括号

16.png

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

17.png


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

实现代码:

class Solution {
    public void tree2strChild(TreeNode root,StringBuilder sb) {
        if(root == null) return ;
        sb.append(root.val);//前序遍历,先将根节点加入可变字符串
        if(root.left==null){//左树为空,还得考虑右树的情况
            if(root.right==null){//如果右树为空,说明当前根节点没有孩子
            //直接返回,因为题目要求把不必要的()省略
                return;
            }else{//右树不为空,加(),这里还在左树,这个()是表示左子树为空
            //因为右树不为空,所有不能省略
                sb.append("()");
            }
        }else{//左树不为空,先加(,然后继续遍历左树,再加)
            sb.append("(");
            tree2strChild(root.left,sb);
            sb.append(")");
        }
        //左树遍历完要遍历右树了
        if(root.right==null){//如果右树为空
            return;//直接返回,因为省略()不会影响字符串与树的映射关系
        }else{//否则,先加(,然后继续遍历右树,再加)
            sb.append("(");
            tree2strChild(root.right,sb);
            sb.append(")");
        }
    }
    public String tree2str(TreeNode root) {
        if(root==null) return null;
        StringBuilder sb = new StringBuilder();
        tree2strChild(root,sb);
        return sb.toString();
    }
}



相关文章
|
3月前
|
Java
【Java集合类面试二十六】、介绍一下ArrayList的数据结构?
ArrayList是基于可动态扩展的数组实现的,支持快速随机访问,但在插入和删除操作时可能需要数组复制而性能较差。
|
3月前
|
存储 Java
Java学习笔记 List集合的定义、集合的遍历、迭代器的使用
Java学习笔记 List集合的定义、集合的遍历、迭代器的使用
|
2天前
|
存储 Java 开发者
在 Java 中,如何遍历一个 Set 集合?
【10月更文挑战第30天】开发者可以根据具体的需求和代码风格选择合适的遍历方式。增强for循环简洁直观,适用于大多数简单的遍历场景;迭代器则更加灵活,可在遍历过程中进行更多复杂的操作;而Lambda表达式和`forEach`方法则提供了一种更简洁的函数式编程风格的遍历方式。
|
28天前
|
算法 前端开发 Java
数据结构与算法学习四:单链表面试题,新浪、腾讯【有难度】、百度面试题
这篇文章总结了单链表的常见面试题,并提供了详细的问题分析、思路分析以及Java代码实现,包括求单链表中有效节点的个数、查找单链表中的倒数第k个节点、单链表的反转以及从尾到头打印单链表等题目。
29 1
数据结构与算法学习四:单链表面试题,新浪、腾讯【有难度】、百度面试题
|
13天前
|
Java 程序员 编译器
Java|如何正确地在遍历 List 时删除元素
从源码分析如何正确地在遍历 List 时删除元素。为什么有的写法会导致异常,而另一些不会。
15 3
|
26天前
|
前端开发 小程序 Java
java基础:map遍历使用;java使用 Patten 和Matches 进行正则匹配;后端传到前端展示图片三种情况,并保存到手机
这篇文章介绍了Java中Map的遍历方法、使用Pattern和matches进行正则表达式匹配,以及后端向前端传输图片并保存到手机的三种情况。
17 1
|
2月前
|
Java
java基础(11)函数重载以及函数递归求和
Java支持函数重载,即在同一个类中可以声明多个同名方法,只要它们的参数类型和个数不同。函数重载与修饰符、返回值无关,但与参数的类型、个数、顺序有关。此外,文中还展示了如何使用递归方法`sum`来计算两个数之间的和,递归的终止条件是当第一个参数大于第二个参数时。
31 1
java基础(11)函数重载以及函数递归求和
|
1月前
|
存储 算法 Java
Java一分钟之-数组的创建与遍历
数组作为Java中存储和操作一组相同类型数据的基本结构,其创建和遍历是编程基础中的基础。通过不同的创建方式,可以根据实际需求灵活地初始化数组。而选择合适的遍历方法,则可以提高代码的可读性和效率。掌握这些基本技能,对于深入学习Java乃至其他编程语言的数据结构和算法都是至关重要的。
22 6
|
10天前
|
存储 NoSQL Redis
Redis常见面试题:ZSet底层数据结构,SDS、压缩列表ZipList、跳表SkipList
String类型底层数据结构,List类型全面解析,ZSet底层数据结构;简单动态字符串SDS、压缩列表ZipList、哈希表、跳表SkipList、整数数组IntSet
|
1月前
【初阶数据结构】打破递归束缚:掌握非递归版快速排序与归并排序
【初阶数据结构】打破递归束缚:掌握非递归版快速排序与归并排序