JAVA-高频面试题汇总:二叉树(上)

「爱情、让人受尽委屈。」 2023-01-01 14:59 261阅读 0赞

## 前言 ##

为了让小伙伴们更好地刷题,我将所有leetcode常考题按照知识点进行了归纳.

## 目录: ##

[JAVA-高频面试题汇总:动态规划][JAVA-]  
[JAVA-高频面试题汇总:字符串][JAVA- 1]  
[JAVA-高频面试题汇总:二叉树(上)][JAVA- 2]  
[JAVA-高频面试题汇总:二叉树(下)][JAVA- 3]  
[JAVA-高频面试题汇总:回溯][JAVA- 4]

## JAVA-高频面试题汇总:二叉树(上): ##

接下来我对树这一知识点进行归纳总结,树的内容总结了二十多道,将分为2篇文章讲解,归纳基于JAVA语言,是我一边复习一边整理的,如有疑惑欢迎交流!  
小编微信: Apollo\_\_\_quan

##### 1.[二叉树中和为某一值的路径][Link 1] #####

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDI3MzMwMg_size_16_color_FFFFFF_t_70_pic_center]

**思路**

1.创建path记录路径，用tar记录路径和（tar = tar - root.val）

2.前序遍历，添加当前节点到path，当tar == 0 且无左右子树时将path加到res

3.遍历左子树与右子树，最后一步删除当前节点表示前两步结束后进行回溯

**注意的点：**

1.ArrayList与LinkedList的remove方法

2.res.add(new ArrayList(path))时传入的应是新的对象而不能时path对象，否则后续path发生变化会影响结果

class Solution { 
            List<List<Integer>> res = new ArrayList<>(); //List是接口 需要ArrayList或LinkedList实现
            List<Integer> path = new ArrayList<>();
        public List<List<Integer>> pathSum(TreeNode root, int sum) { 
            recur(root, sum);
            return res;
        }
        void recur(TreeNode root, int tar){ 
            if(root==null) return;
            path.add(root.val);
            tar = tar - root.val; //值传递,若回溯不改变上一层的tar值,与path相区别
            if(tar == 0 && root.left ==null && root.right ==null){ 
                res.add(new ArrayList(path));//如果直接传入path,传的是path对象,后续对path的改动都会有影响
            }
            recur(root.left, tar);
            recur(root.right, tar);
            path.remove(path.size()-1); //注意path是全局变量,如果回溯需要删除该节点
        }
    }

##### 2.[二叉树的最近公共祖先][Link 2] #####

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDI3MzMwMg_size_16_color_FFFFFF_t_70_pic_center 1]

**思路**

1.递归，可能出现的情况为 ①目标点在root异侧 ②root点为其中一点 ③两侧都没有目标点

2.设置Left与Right遍历左右子树，根据Left与Right讨论上面三种情况，先假设Left与Right的递归合理，否则容易绕晕

class Solution { 
        public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) { 
            if(root == null || root == p || root == q) return root; //为空树或节点为其中一点,直接返回
            TreeNode Left = lowestCommonAncestor(root.left, p, q);
            TreeNode Right = lowestCommonAncestor(root.right, p, q);
            if(Left == null && Right == null) return null; //左右都无目标点,返回null
            else if(Left == null) return Right; //左子树没有,都在右子树,返回右子树遍历结果
            else if(Right == null) return Left; //右子树没有,都在左子树,返回左子树遍历结果
            else return root; //左右都不为null,说明在两边,该点即为最近公共点
        }
    }

3.[二叉树展开为链表][Link 3]

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDI3MzMwMg_size_16_color_FFFFFF_t_70_pic_center 2]

**思路**

推荐[leetcode大佬][leetcode]的解答，思路很清晰

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDI3MzMwMg_size_16_color_FFFFFF_t_70_pic_center 3]

其实是分为三步：

1.首先将根节点的左子树变成链表

2.其次将根节点的右子树变成链表

3.最后将变成链表的右子树放在变成链表的左子树的最右边

这就是一个递归的过程，递归的一个非常重要的点就是：

**不去管函数的内部细节是如何处理的，我们只看其函数作用以及输入与输出**。

对于函数flatten来说：

1.函数作用：将一个二叉树，原地将它展开为链表  
2.输入：树的根节点  
3.输出：无

class Solution { 
        public void flatten(TreeNode root) { 
            if(root == null){ 
                return ;
            }
            //将根节点的左子树变成链表
            flatten(root.left);
            //将根节点的右子树变成链表
            flatten(root.right);
            TreeNode temp = root.right;
            //把树的右边换成左边的链表
            root.right = root.left;
            //记得要将左边置空
            root.left = null;
            //找到树的最右边的节点
            while(root.right != null) root = root.right;
            //把右边的链表接到刚才树的最右边的节点
            root.right = temp;
        }
    }

4.[二叉搜索树与双向链表][Link 4]

这题与第三题乍一看很像，其实差别很大

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDI3MzMwMg_size_16_color_FFFFFF_t_70_pic_center 4]

**思路**

1.中序遍历，一边利用pre指针不断记录节点关系

2.注意最后头尾节点的连接，因为是循环双向链表

class Solution { 
        Node pre = null; 
        Node head; //head为了记录头节点
        public Node treeToDoublyList(Node root) { 
            if(root == null) return pre;
            dfs(root);
            head.left = pre;
            pre.right = head;
            return head;    
        }
        public void dfs(Node node){ 
            if(node == null) return;
            dfs(node.left);
            if(pre != null) pre.right = node; 
            else head = node;  //head记录头节点
            node.left = pre; //如果是头节点则node = head,最终head.left都要覆盖为pre,所以这一步没影响
            pre = node; //pre指针后移到node
            dfs(node.right);
        }
    }

##### 5.[二叉树的右视图][Link 5] #####

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDI3MzMwMg_size_16_color_FFFFFF_t_70_pic_center 5]

**思路**

其实就是层序遍历只记录每层最后一点

class Solution { 
        public List<Integer> rightSideView(TreeNode root) { 
            List<Integer> list = new LinkedList<>();
            Queue<TreeNode> queue=new LinkedList<>();
            if(root == null) return list;
            queue.add(root);
            while(!queue.isEmpty()){ 
                int count = 0;
                int size = queue.size(); //记录长度
                for(int i = 0; i < size; i++){ 
                    TreeNode node = queue.poll();
                    if(node.left != null) queue.add(node.left);
                    if(node.right != null) queue.add(node.right);
                    count++;
                    if(count == size ){   //只添加最后一个数据,与层序遍历区别
                        list.add(node.val);
                    }
                }
            }
            return list;
        }
    }

6.[重建二叉树][Link 6]

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDI3MzMwMg_size_16_color_FFFFFF_t_70_pic_center 6]

**思路**

1.利用前序遍历与中序遍历的特性将树分为左子树与右子树

2.化为子问题进行递归，每一代求解root.left与root.right，并返回root

public class Solution { 
        public TreeNode reConstructBinaryTree(int [] pre,int [] in) { 
            if(pre.length==0) return null;
            TreeNode root =new TreeNode(0);
            root.val=pre[0];  //前序遍历的第一个节点即根节点,后面跟着左子树,然后右子树
            int index=0;
            for(int i=0;i<in.length;i++){  
                if(in[i]==root.val) {   //中序遍历中找根节点,右边的为右子树,左边的为左子树
                    index=i;
                    break;
                }
            }
            //将左子树看成一棵二叉树调用该方法，可以得到左子树根结点，即上面根结点的左子结点
            root.left=reConstructBinaryTree(Arrays.copyOfRange(pre,1,index+1),Arrays.copyOfRange(in,0,index));
           //将右子树看成一棵二叉树调用该方法，可以得到右子树根结点，即上面根结点的右子结点
            root.right=reConstructBinaryTree(Arrays.copyOfRange(pre,index+1,pre.length),Arrays.copyOfRange(in,index+1,in.length));
            return root;
        }
    }

##### 7.[ 树的子结构][Link 7] #####

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDI3MzMwMg_size_16_color_FFFFFF_t_70_pic_center 7]

**思路**

1.先遍历大树，考虑A与B，A.left与B，A.right与B

2.再遍历小树，考虑以当前node1和node2为根的树是否完全相同

class Solution { 
        public boolean isSubStructure(TreeNode A, TreeNode B) { 
            if(A == null || B == null) return false; //题目中A和B为空则都不是子结构
            return recur(A, B) || isSubStructure(A.left, B) || isSubStructure(A.right, B); //先遍历大树，以大树节点开始进行比较，注意recur(A, B)与isSubStructure(A.left, B)的区别，一个是比较当前点，一个是往左子树右子树遍历
        }
         public boolean recur(TreeNode node1, TreeNode node2){  //从当前节点开始判断是否完全相同
             if(node2 == null) return true; /*node2先为空说明node2遍历完了，说明是子结构。 注意判断顺序，若先判断node1==null，会出错 */                                         if(node1 == null || node1.val != node2.val) return false; //node2还没完node1完了，或者值不同，则false
             return recur(node1.left, node2.left) && recur(node1.right, node2.right); //继续判断node1和node2的左右节点
         }
    }

##### 8.[二叉树的镜像][Link 8] #####

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDI3MzMwMg_size_16_color_FFFFFF_t_70_pic_center 8]

注意两种题不同，一种要求返回根节点，一种返回void，只需要交换即可

**解法一（返回TreeNode）**

class Solution { 
          public TreeNode mirrorTree(TreeNode root) { 
            if (root == null) { 
                return null;
            }
            TreeNode leftRoot = mirrorTree(root.right);//以root.right为根，进行镜像，并返回root.right准备当作left
            TreeNode rightRoot = mirrorTree(root.left);//以root.left为根，进行镜像，并返回root.left准备当作right
            root.left = leftRoot; //把原来的root.right（root.right根没变，左右子树已完成镜像）赋值给root.left
            root.right = rightRoot;
            return root; //返回当前根节点
        }
    }

**解法二（返回void）**

public class Solution { 
        public void Mirror(TreeNode root) { 
           if (root==null) return;
           if(root.left==null&&root.right==null) return;
            TreeNode temp=root.right;//交换左右子树
            root.right=root.left;
            root.left=temp;
            Mirror(root.left); //以左右子树为根，继续交换左右子树的左右子树
            Mirror(root.right);
        }
    }

##### 9.[二叉搜索树的后序遍历序列][Link 9] #####

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDI3MzMwMg_size_16_color_FFFFFF_t_70_pic_center 9]

**思路**

1.后序遍历定义： \[ 左子树 | 右子树 | 根节点 \] ，即遍历顺序为 “左、右、根” 。

2.数组最后一个数是根，找出从前往后数第一个大于根的数m(m记录的是小于根的个数)

3.\[0,m-1\]应该都小于根，\[m,length-2\]应该都大于根，符合该标准即为后序遍历

4.**要充分考虑到无左子树或无右子树的情况，因为当无左右子树时，左界本来就已经等于右界，右界再缩小（m-1或j-1），会导致左界>右界**

public class Solution { 
        public boolean VerifySquenceOfBST(int [] sequence) { 
            if (sequence.length==0) return false;
            return recur(sequence,0,sequence.length-1);
        }
        boolean recur(int []arr,int i,int j){ 
            if(i>=j) return true;    //这里的>需要特别注意，i是有可能>j的
            int m=i;            
            while(arr[m]<arr[j]) m++;      //m记录的是小于根的个数
            int p=m;
            while(arr[p]>arr[j]) p++;   //当没有左子树，m=i=0,而最后recur(arr,i,m-1)，i>i-1
                                        //当没有右子树时，m=j=length-1,最后recur(arr,m,j-1)，j>j-1
            return p==j && recur(arr,i,m-1) && recur(arr,m,j-1);
        }
    }

##### 10.[二叉树的深度][Link 10] #####

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDI3MzMwMg_size_16_color_FFFFFF_t_70_pic_center 10]

非常基本的题，没啥好说的，掌握好熟练度。

class Solution { 
        public int maxDepth(TreeNode root) { 
            if(root==null) return 0;
        return Math.max(maxDepth(root.left),maxDepth(root.right))+1;
        }
    }

## 总结 ##

第二部分已完成  
[JAVA-高频面试题汇总:二叉树(下)][JAVA- 3]

[JAVA-]: https://blog.csdn.net/weixin_44273302/article/details/112000020
[JAVA- 1]: https://blog.csdn.net/weixin_44273302/article/details/112436689
[JAVA- 2]: https://blog.csdn.net/weixin_44273302/article/details/112142969
[JAVA- 3]: https://blog.csdn.net/weixin_44273302/article/details/112200568
[JAVA- 4]: https://blog.csdn.net/weixin_44273302/article/details/113423696
[Link 1]: https://leetcode-cn.com/problems/er-cha-shu-zhong-he-wei-mou-yi-zhi-de-lu-jing-lcof/
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDI3MzMwMg_size_16_color_FFFFFF_t_70_pic_center]: /images/20221120/a84041e40b3d438ba810fd92080ddc20.png
[Link 2]: https://leetcode-cn.com/problems/er-cha-shu-de-zui-jin-gong-gong-zu-xian-lcof/
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDI3MzMwMg_size_16_color_FFFFFF_t_70_pic_center 1]: /images/20221120/2e8456999a644df18bc812b6c30c1dc9.png
[Link 3]: https://leetcode-cn.com/problems/flatten-binary-tree-to-linked-list/
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDI3MzMwMg_size_16_color_FFFFFF_t_70_pic_center 2]: /images/20221120/5784a3a6045e43398ec36a611a252c12.png
[leetcode]: https://leetcode-cn.com/problems/flatten-binary-tree-to-linked-list/solution/114-er-cha-shu-zhan-kai-wei-lian-biao-by-ming-zhi-/
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDI3MzMwMg_size_16_color_FFFFFF_t_70_pic_center 3]: /images/20221120/80205eef038b45e3a56ae75ef8fa5c9b.png
[Link 4]: https://leetcode-cn.com/problems/er-cha-sou-suo-shu-yu-shuang-xiang-lian-biao-lcof/
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDI3MzMwMg_size_16_color_FFFFFF_t_70_pic_center 4]: /images/20221120/07cd2c40cc66495792c0c5c4f7e426ad.png
[Link 5]: https://leetcode-cn.com/problems/binary-tree-right-side-view/
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDI3MzMwMg_size_16_color_FFFFFF_t_70_pic_center 5]: /images/20221120/22348b81261e48ba937793a3ba80af64.png
[Link 6]: https://leetcode-cn.com/problems/zhong-jian-er-cha-shu-lcof/
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDI3MzMwMg_size_16_color_FFFFFF_t_70_pic_center 6]: /images/20221120/fb674ecf32af4d979a2d5b59aa66bf0b.png
[Link 7]: https://leetcode-cn.com/problems/shu-de-zi-jie-gou-lcof/
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDI3MzMwMg_size_16_color_FFFFFF_t_70_pic_center 7]: /images/20221120/ed697438215746198a4e99dde7ca8971.png
[Link 8]: https://leetcode-cn.com/problems/er-cha-shu-de-jing-xiang-lcof/
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDI3MzMwMg_size_16_color_FFFFFF_t_70_pic_center 8]: /images/20221120/0d95eac1c313460cb8e39061a1eb05ca.png
[Link 9]: https://leetcode-cn.com/problems/er-cha-sou-suo-shu-de-hou-xu-bian-li-xu-lie-lcof/
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDI3MzMwMg_size_16_color_FFFFFF_t_70_pic_center 9]: /images/20221120/d5b288823e544f5c92819761712cd910.png
[Link 10]: https://leetcode-cn.com/problems/er-cha-shu-de-shen-du-lcof/
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDI3MzMwMg_size_16_color_FFFFFF_t_70_pic_center 10]: /images/20221120/42f51cf808964ef48d9dd4d570538664.png