本文主要是介绍程序员面试金典:二叉树平衡检查、有向路径检查，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
1.二叉树平衡检查
题目描述
实现一个函数，检查二叉树是否平衡，平衡的定义如下，对于树中的任意一个结点，其两颗子树的高度差不超过1。
给定指向树根结点的指针TreeNode* root，请返回一个bool，代表这棵树是否平衡。
import java.util.*;/*
public class TreeNode {int val = 0;TreeNode left = null;TreeNode right = null;public TreeNode(int val) {this.val = val;}
}*/
public class Balance {public boolean isBalance(TreeNode root) {if(root==null) return true;int lf=getHigh(root.left);int lr=getHigh(root.right);if(Math.abs(lf-lr)<=1){return isBalance(root.left)&&isBalance(root.right);}else{return false;}}public int getHigh(TreeNode r){if(r==null) return 0;int left=getHigh(r.left);int right=getHigh(r.right);return left>right?left+1:right+1;}
}2.有向路径检查
题目描述
对于一个有向图，请实现一个算法，找出两点之间是否存在一条路径。
给定图中的两个结点的指针UndirectedGraphNode* a,UndirectedGraphNode* b(请不要在意数据类型，图是有向图),请返回一个bool，代表两点之间是否存在一条路径(a到b或b到a)。
方法1：用集合
本题涉及到一个深度优先遍历的问题，用HashSet作为是否访问到的某个一个标志，然后将该结点的临界点加入递归参数入口进行递归（用ArrayList或者其他集合也能达到类似效果）
import java.util.ArrayList;
import java.util.HashSet;public class Main {public class UndirectedGraphNode {int label = 0;UndirectedGraphNode left = null;UndirectedGraphNode right = null;ArrayList<UndirectedGraphNode> neighbors = new ArrayList<UndirectedGraphNode>();public UndirectedGraphNode(int label) {this.label = label;}}public class Path {public boolean checkPath(UndirectedGraphNode a, UndirectedGraphNode b) {if (null == a || null == b)return false;return checkPathCore(a, b,new HashSet<UndirectedGraphNode>())||checkPathCore(b, a,new HashSet<UndirectedGraphNode>());}public boolean checkPathCore(UndirectedGraphNode a, UndirectedGraphNode b,HashSet<UndirectedGraphNode> map) {if (a == b)return true;map.add(a);// 标记a已被访问for (int i = 0; i < a.neighbors.size(); i++) {if(!map.contains(a.neighbors.get(i))&&checkPathCore(a.neighbors.get(i), b,map))return true;// 发现满足条件的路径立即返回，避免不必要的循环，导致超时。}return false;}}
}
方法2：递归（参考牛客网阿狸不是猫解答）
public class Path {public boolean checkPath(UndirectedGraphNode a, UndirectedGraphNode b) {if (a == null || b == null)return false;return check(a, b) || check(b, a);}public boolean check(UndirectedGraphNode a, UndirectedGraphNode b) {if (a == b)return true;//不让其重复遍历if (a.label == -1)return false;a.label = -1;for (int i = 0; i < a.neighbors.size(); i++) {if (check(a.neighbors.get(i), b))return true;}return false;}}方法3：队列的非递归形式
import java.util.*;/*
public class UndirectedGraphNode {int label = 0;UndirectedGraphNode left = null;UndirectedGraphNode right = null;ArrayList<UndirectedGraphNode> neighbors = new ArrayList<UndirectedGraphNode>();public UndirectedGraphNode(int label) {this.label = label;}
}*/
public class Path {HashMap<UndirectedGraphNode,Boolean> map=new HashMap<UndirectedGraphNode,Boolean>();public boolean checkPath(UndirectedGraphNode a, UndirectedGraphNode b) {if (a == null || b == null)return false;return check(a, b) || check(b, a);}private boolean check(UndirectedGraphNode a, UndirectedGraphNode b) {if(a==b) return true;UndirectedGraphNode p=null;Queue<UndirectedGraphNode> queue=new LinkedList<UndirectedGraphNode>();queue.offer(a);map.put(p,true);while(!queue.isEmpty()){p=queue.poll();for (int i = 0; i <p.neighbors.size(); i++) {if(p.neighbors.get(i)==b) return true;if(!map.containsKey(p.neighbors.get(i))){map.put(p.neighbors.get(i),true);queue.offer(p.neighbors.get(i));}}}return false;}
}这篇关于程序员面试金典:二叉树平衡检查、有向路径检查的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
