- 一、二叉树相关函数的实现
- 1.求二叉树的结点个数
- 2.求二叉树叶子结点的个数
- 3.求二叉树第k层结点的个数
- 4.求二叉树的高度
- 5.求二叉树中值为val的所在结点
- 6.判断该二叉树是不是满二叉树
- 二、二叉树的基础面试题
- 2.1 检查两颗树是否相同。
- 2.2判断是不是另一颗的子树
- 2.3二叉树的最大深度
- 2.4判断二叉树 是否是平衡二叉树
- 2.5判断是否是对称二叉树
- 三、二叉树的进阶面试题
- 3.1 二叉树的构建及遍历。
- 3.2 二叉树的分层遍历 。
- 3.3 给定一个二叉树, 找到该树中两个指定节点的最近公共祖先 。
- 3.4 二叉树搜索树转换成排序双向链表。
- 3.5 根据一棵树的前序遍历与中序遍历构造二叉树。
- 3.6 根据一棵树的中序遍历与后序遍历构造二叉树。
- 3.7 二叉树创建字符串。
- 遍历思路求二叉树结点个数
// 遍历思路-求结点个数 static int size = 0; public void getSize1(TreeNode root){ if (root==null) return; size++; getSize1(root.left); getSize1(root.right); }
- 子问题思路求二叉树结点个数
public int getSize2(TreeNode root){ if (root==null) return 0; return getSize2(root.left)+getSize2(root.right)+1; }2.求二叉树叶子结点的个数
- 遍历思路求二叉树结点个数
static int leafSize = 0; public void getLeafSize1(TreeNode root){ if (root==null) return; if(root.left==null && root.right==null){ leafSize++; } getLeafSize1(root.left); getLeafSize1(root.right); }
- 子问题思路求二叉树结点个数
public int getLeafSize2(TreeNode root){ if (root==null) return 0; if(root.left==null && root.right==null) return 1; return getLeafSize2(root.left)+getLeafSize2(root.right); }3.求二叉树第k层结点的个数
public int getKLevelSize(TreeNode root,int k){ if(root==null ) return 0; if(k ==1) return 1; return getKLevelSize(root.left,k-1)+getKLevelSize(root.right,k-1); }4.求二叉树的高度
public int getHeight(TreeNode root){ if(root==null) return 0; int leftHeight=getHeight(root.left); int rightHeight=getHeight(root.right); return leftHeight>rightHeight?leftHeight+1 :rightHeight+1; }5.求二叉树中值为val的所在结点
public TreeNode find(TreeNode root,char val){ if(root==null) return null; if(root.val==val) return root; TreeNode left=find(root.left,val); if(left!=null) return left; TreeNode right=find(root.right,val); if(right!=null) return right; return null; }6.判断该二叉树是不是满二叉树
// 判断一棵树是不是完全二叉树 public boolean isCompleteTree(TreeNode root){ if(root == null) return true; Queue二、二叉树的基础面试题 2.1 检查两颗树是否相同。queue = new linkedList<>(); queue.offer(root); while (!queue.isEmpty()) { TreeNode cur=queue.poll(); if(cur!=null){ queue.offer(cur.left); queue.offer(cur.right); }else{ break; } } while (!queue.isEmpty()){ TreeNode top=queue.peek(); if(top!=null){ return false; } queue.poll(); } return true; }
- LeetCode OJ 相同的树
class Solution { public boolean isSameTree(TreeNode p, TreeNode q) { //先考虑p q 可能出现的情况 //p为空 q不为空 q 为空p不为空 返回false if(p!=null&&q==null || p==null&& q!=null){ return false; } //p q都为空则返回 true if(p==null && q==null){ return true; } //如果两个都不为空则判断根节点是否相同 若不相同则 返回false if(p.val!=q.val) return false; //递归 判断p q的左右子树是否相同 若同时为true 则这这两颗二叉树也相同 return isSameTree(p.left,q.left)&&isSameTree(p.right,q.right); } }2.2判断是不是另一颗的子树
- OJ另一颗树的子树
class Solution { public boolean isSameTree(TreeNode p, TreeNode q) { //先考虑p q 可能出现的情况 //p为空 q不为空 q 为空p不为空 返回false if(p!=null&&q==null || p==null&& q!=null){ return false; } //p q都为空则返回 true if(p==null && q==null){ return true; } //如果两个都不为空则判断根节点是否相同 若不相同则 返回false if(p.val!=q.val) return false; //递归 判断p q的左右子树是否相同 若同时为true 则这这两颗二叉树也相同 return isSameTree(p.left,q.left)&&isSameTree(p.right,q.right); } public boolean isSubtree(TreeNode root, TreeNode subRoot) { //root一个为空 则返回 false if(root==null ) return false; //先判断这两颗树是否相等 若相等则返回true if(isSameTree(root,subRoot)) return true; //两个树不相等 //这时再判断subRoot是不是root 左子树的子树 如果是则返回true if(isSubtree(root.left,subRoot)) return true; //这时再判断subRoot是不是root 右子树的子树 如果是则返回true if(isSubtree(root.right,subRoot)) return true; //最后都没有返回true 则返回false return false; } }2.3二叉树的最大深度
- 二叉树的最大深度
class Solution { public int maxDepth(TreeNode root) { //结点为null返回0 if(root==null) return 0; int left=maxDepth(root.left);//左子树的最大深度 int right=maxDepth(root.right);//右子树的最大深度 //返回左右子树最大深度+1 return left>right ? left+1 : right+1; } }2.4判断二叉树 是否是平衡二叉树
- 平衡二叉树
平横二叉树:一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过 1 。
自底向上递归的做法类似于后序遍历,对于当前遍历到的节点,先递归地判断其左右子树是否平衡,再判断以当前节点为根的子树是否平衡。如果一棵子树是平衡的,则返回其高度(高度一定是非负整数),否则返回 −1。如果存在一棵子树不平衡,则整个二叉树一定不平衡。
class Solution { public int maxDepth(TreeNode root) { if(root==null) return 0; int left=maxDepth(root.left); //左子树的最大深度 int right=maxDepth(root.right); //右子树的最大深度 //如果左右子树都是平衡二插树 则返回此结点为根节点的树的高度 if(left >=0 && right>=0 &&Math.abs(left-right)<=1){ return left>right ? left+1 : right+1; }else{//若该结点作为根节点的树不是平衡二叉树则放回-1 该结点为空也返回-1 return -1; } } public boolean isBalanced(TreeNode root) { //如果为空返回 true if(root==null) return true; return maxDepth(root)>=0; } }2.5判断是否是对称二叉树
- 对称二叉树
class Solution { public boolean isSymmetricChild(TreeNode p,TreeNode q){ // p q 都为空 返回true if(p==null && q==null) return true; //p为空 q不为空 返回false if(p==null && q!=null) return false; //p不为空 q为空 返回fasle if(p!=null && q==null) return false; // 根节点不同则返回 false if(p.val!=q.val) return false; //递归判断p。left与q。right 和 p。right与q.left是否对称 return (isSymmetricChild(p.left,q.right)&&isSymmetricChild(p.right,q.left)); } public boolean isSymmetric(TreeNode root) { if(root==null ) return true; //左右子树都是对称的 则该根节点的树为对称二叉树 return (isSymmetricChild(root.left,root.right)); } }三、二叉树的进阶面试题 3.1 二叉树的构建及遍历。
- 二叉树的构建和遍历
- 构建结点
1.创建静态变量 i 记录 字符串遍历的位置 ,在函数里创建root结点
2.如果当前字符为#则什么也不做 i++
3.若当前字符不为# 则 让root 结点的值 等于当前字符 i++
4.接下来在递归构建 root 的左右子树
5.最后返回root
import java.util.*; class TreeNode{ public char val; public TreeNode left; public TreeNode right; public TreeNode(char val){ this.val=val; } } public class Main{ public static int i=0; public static TreeNode TreeCreat(String str){ TreeNode root=null; if(str.charAt(i)!='#'){ root=new TreeNode(str.charAt(i)); i++; root.left=TreeCreat(str); root.right=TreeCreat(str); }else{ i++; } return root; } public static void inOrderTraversal(TreeNode root){ if(root ==null) return; inOrderTraversal(root.left); System.out.print(root.val+" "); inOrderTraversal(root.right); } public static void main(String [] args){ Scanner sc=new Scanner(System.in); while (sc.hasNextLine()){ String str=sc.nextLine(); TreeNode root=TreeCreat(str); inOrderTraversal(root); } } }3.2 二叉树的分层遍历 。
- 二叉树的分层遍历
class Solution { public List3.3 给定一个二叉树, 找到该树中两个指定节点的最近公共祖先 。> levelOrder(TreeNode root) { List
> res=new ArrayList<>(); //放最后遍历的结果 if(root ==null) return res; Queue
queue=new linkedList<>(); queue.offer(root); while(!queue.isEmpty()){ int size=queue.size();//用于记录当前层元素的个数 List list=new ArrayList<>(); while(size!=0){ TreeNode cur=queue.poll(); list.add(cur.val); if(cur.left!=null) queue.offer(cur.left); if(cur.right!=null) queue.offer(cur.right); size--; } res.add(list); } return res; } }
- 二叉树的最近公共祖先
- 思路
1.判断当前root是否等于 p q 等于直接返回
2.递归遍历root的左右子树 (如果找到就返回那个结点,找不到返回null)
3.最终情况分为四种:a.左右都不为空 则直接返回root(p q在两边) b.左右一个为空一个不为空则返回不为空的(若p q 都在左边 或者 p q都在右边)c。其他情况返回null;
class Solution { public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) { if(root==null) return null; if(root ==q || root==p) return root; //如果root==p ||q 则直接返回root TreeNode left=lowestCommonAncestor(root.left,p, q); //先递归找左子树 TreeNode right=lowestCommonAncestor(root.right, p, q);//递归找右子树 if(left!=null &&right!=null){ //左右子树都不为null 返回 root return root; }else if(left==null && right!=null){//左右子树谁不为空返回谁 return right; }else if(left!=null && right==null){ return left; }else{//left==null && right==null return null; } } }3.4 二叉树搜索树转换成排序双向链表。
- 二叉树搜索树转换成排序双向链表
public class Solution { TreeNode prev=null;//记录先前结点 public void ConvertChild(TreeNode pcur) { if(pcur==null) return; //采用中序遍历 合成链表 链表才有序 ConvertChild(pcur.left); pcur.left=prev; //让当前结点的left指向他的先前结点 if(prev!=null){ //prev为空 则它不需要向后指 (第一次) prev.right=pcur;//让先前结点指向自己 } prev=pcur;//先前结点向后移动 ConvertChild(pcur.right); } //结点的left 记录先前结点 right记录后继结点 public TreeNode Convert(TreeNode pRootOfTree) { if(pRootOfTree==null) return null; ConvertChild(pRootOfTree); //找双向链表的头结点 返回双向连边 TreeNode head=pRootOfTree; while(head.left!=null){ head=head.left; } return head; } }3.5 根据一棵树的前序遍历与中序遍历构造二叉树。
- 根据前序和中序构建二叉树
class Solution { public int pi=0; public TreeNode buildTreeChild(int[] preorder, int[] inorder,int begin ,int end) { if(begin>end) return null; //说明遍历结束 //构建树 TreeNode root= new TreeNode(preorder[pi]); int ri=findIndex(inorder,begin,end,preorder[pi]) ; //找先序中pi下标对应值在中序遍历中的值 pi++; //递归构建左子树 root.left=buildTreeChild(preorder,inorder,begin,ri-1); //递归构建右子树 root.right=buildTreeChild(preorder,inorder,ri+1,end); return root; } //查找中序遍历中 begin end 之间 值为 key 的下标 public int findIndex(int[] inorder,int begin,int end,int key) { for(int i = 0;i <= end;i++) { if(inorder[i] == key) { return i; } } return -1; } public TreeNode buildTree(int[] preorder, int[] inorder) { return buildTreeChild(preorder,inorder,0,inorder.length-1); } }3.6 根据一棵树的中序遍历与后序遍历构造二叉树。
- 根据中序和后序遍历二叉树
class Solution { public static int pi; public TreeNode buildTreeChild(int[] inorder, int[] postorder,int begin,int end){ if(begin>end) return null; TreeNode root=new TreeNode(postorder[pi]); int ri=find(inorder,begin,end,postorder[pi]); pi--; root.right=buildTreeChild(inorder,postorder,ri+1,end); root.left=buildTreeChild(inorder,postorder,begin,ri-1); return root; } public int find(int[] inorder,int begin,int end,int key) { for(int i = 0;i <= end;i++) { if(inorder[i] == key) { return i; } } return -1; } public TreeNode buildTree(int[] inorder, int[] postorder) { pi=postorder.length-1; return buildTreeChild(inorder,postorder,0,inorder.length-1); } }3.7 二叉树创建字符串。
- 二叉树创建字符串
- 思路
1.先序遍历 如果当前为空直接return
2.不为空放入StringBuilder 中
3.判断左子树情况{ [左不为空: 先加 ‘(’ 、放数据、’)’ ]、[左为空 右也为空:直接return]、[左为空 右不为空:将 ‘()’放入]}
4.判断右子树情况{[右为空 :直接return]、[右不为空:先加 ‘(’ 、放数据、’)’ ]}
class Solution { public void tree2strChild(TreeNode t,StringBuilder sb){ if(t==null) return; sb.append(t.val);//现将t的值放入 sb 中 if(t.left==null){ if(t.right==null){ //左为空 右也为空 return; }else{//最为空 右不为空 sb.append("()"); } }else{//如果做不为空 sb.append("("); tree2strChild(t.left,sb); sb.append(")"); } if(t.right==null){ //右为空 return ; }else{//右不为空 sb.append("("); tree2strChild(t.right,sb); sb.append(")"); } } public String tree2str(TreeNode root) { StringBuilder sb=new StringBuilder(); tree2strChild(root,sb); return sb.toString(); } }
欢迎分享,转载请注明来源:内存溢出
评论列表(0条)