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

矫情吗；* 2023-01-02 04:28 223阅读 0赞

## 前言 ##

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

## 目录: ##

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

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

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

##### 11.[二叉树的下一个节点][Link 1] #####

![在这里插入图片描述][20210104203455261.png_pic_center]

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

**思路**

仔细观察，可以把中序下一结点归为四种类型：

1.  有右子树，下一结点是右子树中的最左结点，例如 B，下一结点是 H
2.  无右子树，且结点是该结点父结点的左子树，则下一结点是该结点的父结点，例如 H，下一结点是 E
3.  无右子树，且结点是该结点父结点的右子树，则我们一直沿着父结点追朔，直到找到某个结点是其父结点的左子树，如果存在这样的结点，那么这个结点的父结点就是我们要找的下一结点。例如 I，下一结点是 A。
4.  无右子树，且结点是该结点父结点的右子树，则我们一直沿着父结点追朔，然而找不到某个结点是其父结点的左子树，例如 G，并没有符合情况的结点，所以 G 没有下一结点
    
    其中3、4代码可以合并成一种 （pNode.next!=null && pNode.next.left==pNode）
    
        /* public class TreeLinkNode { int val; TreeLinkNode left = null; TreeLinkNode right = null; TreeLinkNode next = null; TreeLinkNode(int val) { this.val = val; } } */
        public class Solution { 
            public TreeLinkNode GetNext(TreeLinkNode pNode)
            { 
                if(pNode==null) return null;
                if(pNode.right != null){   //第一种情况
                    TreeLinkNode cur = pNode.right; 
                    while(cur.left != null) { 
                    cur = cur.left;
                    }
                    return cur;
                }
                else{ 
                    if(pNode.next!=null && pNode.next.left==pNode){  //第二种情况，注意pNode.next!=null
                        return pNode.next;
                        }
                    else{ 
                        TreeLinkNode node2=pNode;
                        while(node2.next!=null&&node2!=node2.next.left) //包含了第三第四种情况
                        {   
                            node2=node2.next;
                        }
                        return node2.next;
                        }
                    }
            }
        }

##### 12.[对称二叉树][Link 2] #####

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

**思路**

重点是要讨论left.left,right.right 以及left.right,right.left 所以最好把左右子树拿来做递归函数的参数

boolean isSymmetrical(TreeNode pRoot)
        { 
            if(pRoot == null) return true; //空树为true
            return duicheng(pRoot.left, pRoot.right); //从左右子树单独递归，这个思路要牢记
        }
        public boolean duicheng(TreeNode left, TreeNode right){ 
            if(left==null&&right==null) return true; //判空要放前面，否则后面会空指针
            if(left==null||right==null||left.val!=right.val) return false;//判空要放前面，否则后面会空指针
            return duicheng(left.left,right.right)&&duicheng(left.right,right.left);
        }

##### 13.[对称二叉树][Link 2] #####

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

**思路**

重点是要讨论left.left,right.right 以及left.right,right.left 所以最好把左右子树拿来做递归函数的参数

##### 14.[之字形打印二叉树 ][Link 3] #####

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

**思路**

1.考虑每一层打印顺序的问题，层序遍历是基础

2.把题中顺序都当作**出栈顺序**。创建两个栈，控制奇数偶数时左子树右子树的入栈顺序，来实现题中出栈顺序

public class Solution { 
        Stack<TreeNode> stack1=new Stack<>();
        Stack<TreeNode> stack2=new Stack<>();  //创建两个栈
        ArrayList<Integer> res=new ArrayList<>();
        ArrayList<ArrayList<Integer> > list=new ArrayList<>();
        public ArrayList<ArrayList<Integer> > Print(TreeNode pRoot) { 
           if(pRoot==null) return list;
            stack1.add(pRoot);
            while(!stack1.isEmpty()||!stack2.isEmpty()){  //两栈不都为空时说明没遍历完
                while(!stack1.isEmpty()){  
                    TreeNode node = stack1.pop();
                    if(node.left!=null) stack2.add(node.left);  //根据规律，奇数时左子树先进栈
                    if(node.right!=null) stack2.add(node.right);
                    res.add(node.val);
                }
                list.add(res);
                res=new ArrayList<>();
                while(!stack2.isEmpty()){ 
                    TreeNode node = stack2.pop();
                    if(node.right!=null) stack1.add(node.right); //根据规律，偶数时右子树先进栈
                    if(node.left!=null) stack1.add(node.left);
                    res.add(node.val);
                }
               
                if(!res.isEmpty()) list.add(res); //避免最后一次遍历可能stack2为空跳过了，此时res是空列表被加入
                res=new ArrayList<>();
            }
            return list;
        }
    }

##### 15.[二叉搜索树的第k大节点][k] #####

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

**思路**

1.注意返回的是树还是节点

2.考虑提前返回的解法

class Solution {  
            int num = 0, res = 0; //num计数，res记录数值
        public int kthLargest(TreeNode root, int k) { 
            recur(root, k);
            return res;
        }
        public void recur(TreeNode node, int k){ 
            if(node == null) return;
            recur(node.right, k); //因为是降序，从右子树开始遍历
            if(num == k) return; //提前返回，若num==k，则接下来的判断都是return；，一层层返回退出递归
            if(++num == k) {  
                res = node.val;
            }
            recur(node.left, k);
        }
    }

##### 16.[最大二叉树][Link 4] #####

![在这里插入图片描述][20210108163340889.png_pic_center]

**思路**

简单解法，遍历数组找到最大值，最大值左边的为左子树，右边的是右子树。这种解法时间复杂度O(n^2)

如果有更好解法的欢迎评论哈，后续有想到我也会补充

class Solution { 
        public TreeNode constructMaximumBinaryTree(int[] nums) { 
            if(nums.length ==0) return null;
            int max = nums[0], index = 0;
            for(int i = 0; i < nums.length; i++){  //遍历数组找到最大值并记录位置
                if(nums[i] >max){ 
                    max = nums[i];
                    index = i;
                }
            }
            TreeNode Left =  constructMaximumBinaryTree(Arrays.copyOfRange(nums, 0, index)); //左子树
            TreeNode Right =  constructMaximumBinaryTree(Arrays.copyOfRange(nums, index + 1, nums.length)); //右子树
            TreeNode node = new TreeNode(max);
            node.left = Left;
            node.right = Right;
            return node; //注意返回当前节点
        }
    }

##### 17.[不同的二叉搜索树 II][II] #####

这题乍一看和[不同的二叉搜索树][Link 5]类似，注意区分，前者是用动态规划解的

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

**思路**

递归，附上[官方解法][Link 6]  
![image-20210108110604709][]

class Solution { 
        public List<TreeNode> generateTrees(int n) { 
            if (n == 0) { 
                return new LinkedList<TreeNode>();
            }
            return generateTrees(1, n);
        }
    
        public List<TreeNode> generateTrees(int start, int end) { 
            List<TreeNode> allTrees = new LinkedList<TreeNode>();
            if (start > end) { 
                allTrees.add(null);
                return allTrees;
            }
    
            // 枚举可行根节点
            for (int i = start; i <= end; i++) { 
                // 获得所有可行的左子树集合
                List<TreeNode> leftTrees = generateTrees(start, i - 1);
    
                // 获得所有可行的右子树集合
                List<TreeNode> rightTrees = generateTrees(i + 1, end);
    
                // 从左子树集合中选出一棵左子树，从右子树集合中选出一棵右子树，拼接到根节点上
                for (TreeNode left : leftTrees) { 
                    for (TreeNode right : rightTrees) { 
                        TreeNode currTree = new TreeNode(i);
                        currTree.left = left;
                        currTree.right = right;
                        allTrees.add(currTree);
                    }
                }
            }
            return allTrees;
        }
    }

##### 18.[将有序数组转换为二叉搜索树][Link 7] #####

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

**思路**

1.因为本题要求高度平衡，所以选择升序序列的中间元素作为根节点

2.如果数组是奇数长度，结果唯一，如果是偶数，结果不唯一（可以选择中间左边或中间右边节点作为根）。

class Solution { 
        public TreeNode sortedArrayToBST(int[] nums) { 
            return dfs(nums, 0, nums.length - 1);
        }
    
        private TreeNode dfs(int[] nums, int lo, int hi) { 
            if (lo > hi) { 
                return null;
            } 
            // 以升序数组的中间元素作为根节点 root。
            int mid = lo + (hi - lo) / 2;
            TreeNode root = new TreeNode(nums[mid]);
            // 递归的构建 root 的左子树与右子树。
            root.left = dfs(nums, lo, mid - 1);
            root.right = dfs(nums, mid + 1, hi); 
            return root;
        }
    }

##### 19.[有序链表转换二叉搜索树][Link 8] #####

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

**思路**

1.与上一题对比，将通过数组索引定位中心元素改成快慢指针法找中心元素即可

2.快指针是慢指针的两倍速率，所以快指针达到尾结点时，慢指针到达中间节点

class Solution { 
        ListNode globalHead;
    
        public TreeNode sortedListToBST(ListNode head) { 
            globalHead = head;
            int length = getLength(head);
            return buildTree(0, length - 1);
        }
    
        public int getLength(ListNode head) { 
            int ret = 0;
            while (head != null) { 
                ++ret;
                head = head.next;
            }
            return ret;
        }
    
        public TreeNode buildTree(int left, int right) { 
            if (left > right) { 
                return null;
            }
            int mid = (left + right + 1) / 2;
            TreeNode root = new TreeNode();
            root.left = buildTree(left, mid - 1);
            root.val = globalHead.val;
            globalHead = globalHead.next;
            root.right = buildTree(mid + 1, right);
            return root;
        }
    }

##### 20.[将二叉搜索树变平衡][Link 9] #####

![image-20210108153340441.pn][]

**思路**

通用的方法，先将一棵树中序遍历出，然后按照前两题的方法，把中位数当根节点，递归构造二叉树

class Solution { 
        public TreeNode balanceBST(TreeNode root) { 
            List<Integer> list = new ArrayList<>();
            zhongxu(list, root); // 中序遍历构造有序链表
            return BuildTree(list, 0, list.size() - 1);  // 有序链表构造平衡二叉树
        }
        public void zhongxu(List<Integer> list, TreeNode node){    //有序链表构造平衡二叉树
            if(node == null) return;
            zhongxu(list, node.left);
            list.add(node.val);
            zhongxu(list, node.right);
        }
        public TreeNode BuildTree(List<Integer> list, int start, int end){ 
            if(start > end) return null;
            int mid = start + (end - start) / 2;
            TreeNode root = new TreeNode(list.get(mid)); // 中间节点为root
            root.left = BuildTree(list, start, mid-1); // 递归构造左右子树
            root.right = BuildTree(list, mid+1, end);
            return root; // 返回root
        }
    }

**思路**

通用的方法，先将一棵树中序遍历出，然后按照前两题的方法，把中位数当根节点，递归构造二叉树

## 总结 ##

至此，二叉树常考题归纳完毕，后续会有其他类型题的更新！  
[JAVA-高频面试题汇总:动态规划][JAVA-]  
[JAVA-高频面试题汇总:字符串][JAVA- 1]  
[JAVA-高频面试题汇总:二叉树(上)][JAVA- 2]  
[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://www.nowcoder.com/practice/9023a0c988684a53960365b889ceaf5e?tpId=13&&tqId=11210&rp=1&ru=/ta/coding-interviews&qru=/ta/coding-interviews/question-ranking
[20210104203455261.png_pic_center]: /images/20221120/3d3b88be0bb44be39d5862fdb7b831db.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDI3MzMwMg_size_16_color_FFFFFF_t_70]: /images/20221120/02d4865b540146c4b1ca72600de840a0.png
[Link 2]: https://leetcode-cn.com/problems/symmetric-tree/
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDI3MzMwMg_size_16_color_FFFFFF_t_70_pic_center]: /images/20221120/85cd81ba66944eddbbb26d189de5118b.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDI3MzMwMg_size_16_color_FFFFFF_t_70_pic_center 1]: /images/20221120/5d4e8141f4b3433a9bffb7be7ddcf424.png
[Link 3]: https://leetcode-cn.com/problems/cong-shang-dao-xia-da-yin-er-cha-shu-iii-lcof/
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDI3MzMwMg_size_16_color_FFFFFF_t_70_pic_center 2]: /images/20221120/1f72b1a59bbc4a0aa95a76bcc618974c.png
[k]: https://leetcode-cn.com/problems/er-cha-sou-suo-shu-de-di-kda-jie-dian-lcof/
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDI3MzMwMg_size_16_color_FFFFFF_t_70_pic_center 3]: /images/20221120/0be3521de9f44ceb8b679ef567e09b86.png
[Link 4]: https://leetcode-cn.com/problems/maximum-binary-tree/
[20210108163340889.png_pic_center]: /images/20221120/7b83919963c34caba226100f02a0835d.png
[II]: https://leetcode-cn.com/problems/unique-binary-search-trees-ii/
[Link 5]: https://leetcode-cn.com/problems/unique-binary-search-trees/
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDI3MzMwMg_size_16_color_FFFFFF_t_70_pic_center 4]: /images/20221120/4314d1f691aa4a3c9a36fa8755dbd39d.png
[Link 6]: https://leetcode-cn.com/problems/unique-binary-search-trees-ii/solution/bu-tong-de-er-cha-sou-suo-shu-ii-by-leetcode-solut/
[image-20210108110604709]: /images/20221120/8816064cb264423caee5140c452e95cb.png
[Link 7]: https://leetcode-cn.com/problems/convert-sorted-array-to-binary-search-tree/solution/jian-dan-di-gui-bi-xu-miao-dong-by-sweetiee/
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDI3MzMwMg_size_16_color_FFFFFF_t_70_pic_center 5]: /images/20221120/f178cf7c34024b4bb46574aaceadd017.png
[Link 8]: https://leetcode-cn.com/problems/convert-sorted-list-to-binary-search-tree/solution/you-xu-lian-biao-zhuan-huan-er-cha-sou-suo-shu-1-3/
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDI3MzMwMg_size_16_color_FFFFFF_t_70_pic_center 6]: /images/20221120/2451c021731e403bb812c5fa99dcbc9d.png
[Link 9]: https://leetcode-cn.com/problems/balance-a-binary-search-tree/solution/shou-si-avlshu-wo-bu-guan-wo-jiu-shi-yao-xuan-zhua/
[image-20210108153340441.pn]: /images/20221120/2d25fbfcab8e4c1691b903683cb56de4.png