前言
为了让小伙伴们更好地刷题,我将所有leetcode常考题按照知识点进行了归纳.
目录:
JAVA-高频面试题汇总:动态规划
JAVA-高频面试题汇总:字符串
JAVA-高频面试题汇总:二叉树(上)
JAVA-高频面试题汇总:二叉树(下)
JAVA-高频面试题汇总:回溯
JAVA-高频面试题汇总:二叉树(下):
接下来我对树这一知识点进行归纳总结,树的内容总结了二十多道,将分为2篇文章讲解,归纳基于JAVA语言,是我一边复习一边整理的,如有疑惑欢迎交流!
小编微信: Apollo___quan
11.二叉树的下一个节点
思路
仔细观察，可以把中序下一结点归为四种类型：
-
有右子树，下一结点是右子树中的最左结点，例如 B，下一结点是 H
-
无右子树，且结点是该结点父结点的左子树，则下一结点是该结点的父结点，例如 H，下一结点是 E
-
无右子树，且结点是该结点父结点的右子树，则我们一直沿着父结点追朔，直到找到某个结点是其父结点的左子树，如果存在这样的结点，那么这个结点的父结点就是我们要找的下一结点。例如 I，下一结点是 A。
-
无右子树，且结点是该结点父结点的右子树，则我们一直沿着父结点追朔，然而找不到某个结点是其父结点的左子树，例如 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.对称二叉树
思路
重点是要讨论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.对称二叉树
思路
重点是要讨论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);
}
14.之字形打印二叉树
思路
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大节点
思路
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.最大二叉树
思路
简单解法，遍历数组找到最大值，最大值左边的为左子树，右边的是右子树。这种解法时间复杂度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
这题乍一看和不同的二叉搜索树类似，注意区分，前者是用动态规划解的
思路
递归，附上官方解法
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.将有序数组转换为二叉搜索树
思路
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.有序链表转换二叉搜索树
思路
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.将二叉搜索树变平衡
思路
通用的方法，先将一棵树中序遍历出，然后按照前两题的方法，把中位数当根节点，递归构造二叉树
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
}
}
思路
通用的方法，先将一棵树中序遍历出，然后按照前两题的方法，把中位数当根节点，递归构造二叉树
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-高频面试题汇总:二叉树(下)
381
被折叠的 条评论
为什么被折叠?
到【灌水乐园】发言
