目录

一、判断是不是二叉搜索树1.1 题目1.2 题解 二、判断是不是完全二叉树2.1 题目2.2 题解 三、判断是不是平衡二叉树3.1 题目3.2 题解 四、二叉搜索树的最近公共祖先4.1 题目4.2 题解 五、在二叉搜索树中找到两个节点的最近公共祖先5.1 题目5.2 题解 六、序列化二叉树6.1 题目6.2 题解 七、重建二叉树7.1 题目7.2 题解 八、二叉树的右视图8.1 题目8.2 题解

一、判断是不是二叉搜索树

1.1 题目

1.2 题解

思路：二叉搜索树的中序遍历是升序的，pre保存当前节点的前一个被遍历的节点值，如果pre>当前节点的值，直接返回false，否则更新pre为当前节点，继续遍历

代码执行过程图解：

代码：

public class Solution {int pre=Integer.MIN_VALUE;public boolean isValidBST (TreeNode root) {if(root==null) return true;if(!isValidBST(root.left))return false;if(root.val<pre)return false;pre=root.val;return isValidBST(root.right);}}

二、判断是不是完全二叉树

2.1 题目

2.2 题解

使用层序遍历的方式判断是否为完全二叉树

具体步骤：

step1：将根节点加入队列

step2：从队列中弹出节点，如果该节点不为null，则将该节点的左右子节点入队

step3：如果从队列中弹出的节点为null，说明遍历到了最下层，将队列中其他元素依次出队，如果在出队过程中，遇到非null节点，则不符合完全二叉树的要求，返回false

代码：

public boolean isCompleteTree (TreeNode root) {Queue<TreeNode> queue=new LinkedList<>();queue.add(root);while(!queue.isEmpty()){TreeNode tmp=queue.poll();if(tmp!=null){queue.add(tmp.left);queue.add(tmp.right);}else {//当前节点为nullwhile(!queue.isEmpty()){//遇到后面节点不是null，直接返回falseif(queue.poll()!=null){return false;}}}}return true;}

三、判断是不是平衡二叉树

3.1 题目

3.2 题解

思路：在求树的高度的过程中，顺便判断下该树是不是平衡二叉树，在求某棵子树的高度时，如果发现该子树的左右高度差大于1，那么说明该子树就不是不哼二叉树，那么整棵树也一定不是平衡二叉树

代码：

public boolean IsBalanced_Solution(TreeNode root) {return height(root)>=0;}public int height(TreeNode root){if(root==null) return 0;int leftH=height(root.left);int rightH=height(root.right);if(leftH>=0 && rightH>=0 && Math.abs(leftH-rightH)<=1){//该棵树平衡二叉树，返回该树的高度return leftH>rightH?leftH+1:rightH+1;}else {//遇到某棵子树不是平衡二叉树，直接向上层返回-1return -1;}}

四、二叉搜索树的最近公共祖先

4.1 题目

4.2 题解

思路：利用二叉搜索树的性质，比较根节点和p，q的值，如果root.val与p，q其中一个相等，直接返回root.val，如果p，q都小于root.val，说明p，q都位于root的左子树上，是原问题的一个子问题，那么递归的进入左子树寻找最近公共祖先

如果p，q都大于root.val，说明p，q都位于root的右子树上，那么递归的进入右子树寻找最近公共祖先，如果p，q一个大于root.val,一个小于root.val，说明p，q分别位于root的左右上，那么这两棵树的最近公共祖先就是root

代码：

public int lowestCommonAncestor (TreeNode root, int p, int q) {if(root==null) return -1;if(root.val==p || root.val==q)return root.val;if((root.val>p && root.val<q) ||(root.val<p && root.val>q)){return root.val;}if(root.val<p && root.val<q){return lowestCommonAncestor(root.right,p,q);}return lowestCommonAncestor(root.left,p,q);}

五、在二叉搜索树中找到两个节点的最近公共祖先

5.1 题目

5.2 题解

思路：

step1：如果root为null，直接返回-1，代表不存在公共祖先

step2：如果o1和o2其中一个与root.val相等，说明当前root就是o1和o2的最近公共祖先

step3：如果o1和o2与当前root.val都不相等，就递归左右子树，在root的左右子树中分别寻找与o1和o2相等的节点

step4：如果o1和o2分别出现在root的左右子树上，说明root就是最近公共祖先

step5：如果两个节点都出现在左子树，则说明最低公共祖先在左子树中，否则在右子树。

代码：

public int lowestCommonAncestor (TreeNode root, int o1, int o2) {if(root==null) return -1;if(root.val==o1 || root.val==o2) return root.val;int left=lowestCommonAncestor(root.left,o1,o2);int right=lowestCommonAncestor(root.right,o1,o2);if(left>0 && right>0){return root.val;}else if(left>0){return left;}else if(right>0){return right;}return -1;}

六、序列化二叉树

6.1 题目

6.2 题解

思路：使用层序遍历对二叉树进行序列化和反序列化

序列化：常规的层序遍历逻辑，用值为INF的节点代表是空节点

反序列化：先将根节点入队，然后每次从队列中取出元素时，同时从序列化字符中取两个值，作为左右节点，查是否为 INF，若不为 INF 则构建对应节点；

代码：

import java.util.*;public class Solution {int INF=0x3f3f3f3f;TreeNode emptyNode=new TreeNode(INF);String Serialize(TreeNode root) {if(root==null) return "";StringBuffer sb=new StringBuffer();Deque<TreeNode> d=new ArrayDeque<>();d.addLast(root);while(!d.isEmpty()){TreeNode poll=d.pollFirst();sb.append(poll.val+"-");if(!poll.equals(emptyNode)){d.addLast(poll.left!=null?poll.left:emptyNode);d.addLast(poll.right!=null?poll.right:emptyNode);}} return sb.toString();}TreeNode Deserialize(String str) {if(str.equals("")) return null;String[] ss=str.split("-");int n=ss.length;Deque<TreeNode> d=new ArrayDeque<>();TreeNode root=new TreeNode(Integer.parseInt(ss[0]));d.addLast(root);for(int i=1;i<n-1;i+=2){TreeNode tmp=d.pollFirst();int a=Integer.parseInt(ss[i]);int b=Integer.parseInt(ss[i+1]);if(a!=INF){tmp.left=new TreeNode(a);d.addLast(tmp.left);}if(b!=INF){tmp.right=new TreeNode(b);d.addLast(tmp.right);}}return root;}}

七、重建二叉树

7.1 题目

7.2 题解

思路：

代码：

public class Solution {public int pi=0;HashMap<Integer,Integer> map=new HashMap<>();public void inorder(int[] vin){for(int i=0;i<vin.length;i++){map.put(vin[i],i);}}public TreeNode reConstructBinaryTree(int [] pre,int [] vin) {inorder(vin);return process(pre,vin,0,vin.length-1);}public TreeNode process(int[] pre,int[] vin,int ib,int ie){if(ib>ie) return null;TreeNode root=new TreeNode(pre[pi]);int rootIndex=map.get(pre[pi++]);root.left=process(pre,vin,ib,rootIndex-1);root.right=process(pre,vin,rootIndex+1,ie);return root;}}

八、二叉树的右视图

8.1 题目

8.2 题解

解决本题主要 分两个步骤：

根据前序和中序构建出二叉树对二叉树进行层次遍历，找到每一层的最右侧的节点

变量size记录的是当前遍历到的层的节点数，我们在入队的时候的顺序是：从左到右依次将当前层的节点加入到队列中，所以在出队的时候，当前层的最右侧的节点一定是该层所有节点中最后一个出队列的

故我们可根据这一特点，增设一个判断条件，但size为0时，此时上一次出的元素就是当前层的最右侧的元素

代码：

import java.util.*;public class Solution {/*** 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可* 求二叉树的右视图* @param xianxu int整型一维数组 先序遍历* @param zhongxu int整型一维数组 中序遍历* @return int整型一维数组*/int preIndex=0;HashMap<Integer,Integer> map=new HashMap<>();public void RootIndex(int[] inorder){for (int i = 0; i < inorder.length; i++) {map.put(inorder[i],i);}}public ArrayList<Integer> rightSideView(TreeNode root) {ArrayList<Integer> res = new ArrayList<Integer>();Queue<TreeNode> q = new LinkedList<TreeNode>();q.offer(root);while(!q.isEmpty()){//队列中的大小即是这一层的节点树int size = q.size();while(size-- != 0){TreeNode temp = q.poll(); if(temp.left != null)q.offer(temp.left);if(temp.right != null)q.offer(temp.right);//最右元素if(size == 0)res.add(temp.val);}}return res;}public int[] solve (int[] xianxu, int[] zhongxu) {TreeNode root=buildTree(xianxu,zhongxu);ArrayList<Integer> tmp=rightSideView(root);int[] arr=new int[tmp.size()];for(int i=0;i<tmp.size();i++){arr[i]=tmp.get(i);}return arr;}public TreeNode buildTree(int[] xianxu,int[] zhongxu ){RootIndex(zhongxu);return buildTreeChild(xianxu,zhongxu,0,zhongxu.length-1);}public TreeNode buildTreeChild(int[] xianxu,int[] zhongxu,int inbegin,int inend){if(inbegin>inend){return null;}TreeNode root=new TreeNode(xianxu[preIndex]);int ri=map.get(xianxu[preIndex]);preIndex++;root.left=buildTreeChild(xianxu,zhongxu,inbegin,ri-1);root.right=buildTreeChild(xianxu,zhongxu,ri+1,inend);return root;}}

二叉树(二)：判断是不是二叉搜索树 判断是不是完全二叉树 判断是不是平衡二叉树 二叉搜索树的最近公共祖先 在二叉搜索树中找到两个节点的最近公共祖先 序列化二叉树 重建二叉树 输出二叉树的右视图

如果觉得《二叉树(二)：判断是不是二叉搜索树 判断是不是完全二叉树 判断是不是平衡二叉树 二》对你有帮助，请点赞、收藏，并留下你的观点哦！