目录
一、判断是不是二叉搜索树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;}}
二叉树(二):判断是不是二叉搜索树 判断是不是完全二叉树 判断是不是平衡二叉树 二叉搜索树的最近公共祖先 在二叉搜索树中找到两个节点的最近公共祖先 序列化二叉树 重建二叉树 输出二叉树的右视图
如果觉得《二叉树(二):判断是不是二叉搜索树 判断是不是完全二叉树 判断是不是平衡二叉树 二》对你有帮助,请点赞、收藏,并留下你的观点哦!