摘要：题目目录基础面试题二叉树的前序遍历二叉树的中序遍历二叉树的后续遍历结果相同的树另一棵树的子树二叉树的最大深度平衡二叉树判断对称二叉树进阶面试题二叉树的遍历及构建二叉树的分层遍历二叉树的最近公共祖先二叉搜索树与双向链表从前序
题目：在线OJ
思考：
首先，我们要了解，前序遍历就是按照顺序：根节点—左子树—右子树的方式遍历树(根左右)
在访问左右子树的时候，按照上述同样的方法遍历，因此我们可以考虑使用递归来解决
画图分析：
代码实现：
public List<Integer> preorderTraversal(TreeNode root) { //创建一个 List List<Integer> result = new ArrayList<>(); if(root == null){ //空树返回 一个空 List(元素个数为空，但不是null) return result; } //访问根节点 //把元素 add 到 List中 result.add(root.val); //递归遍历左子树,把左子树的遍历结果加入到List中 result.addAll(preorderTraversal(root.left)); //递归遍历右子树,把右子树的遍历结果加入到List中 result.addAll(preorderTraversal(root.right)); return result;}题目：在线OJ
思考：
中序遍历是按照顺序：左子树遍历—根节点—右子树遍历的方式来遍历树(左根右)
同先序遍历一样，使用递归解决
画图分析：
代码实现：
public List<Integer> inorderTraversal(TreeNode root) { //创建一个List List<Integer> result = new ArrayList<>(); //空树判断 if(root == null){ return result; } //递归遍历左子树 result.addAll(inorderTraversal(root.left)); //根节点 result.add(root.val); //递归遍历右子树 result.addAll(inorderTraversal(root.right)); return result;}题目：在线OJ
思考：
后续遍历按照顺序：左子树遍历—右子树遍历—根节点的遍历方式来遍历树的(左右根)
实现过程参考前序遍历
代码实现：
public List<Integer> postorderTraversal(TreeNode root) { //创建一个List List<Integer> result = new ArrayList<>(); //空树判断 if(root == null){ return result; } //左子树遍历 result.addAll(postorderTraversal(root.left)); //右子树遍历 result.addAll(postorderTraversal(root.right)); //根节点 result.add(root.val); return result;}题目：在线OJ
思考：
以上条件均满足时，则说明这两棵树相同
画图分析：
代码实现：
public boolean isSameTree(TreeNode p, TreeNode q) { //两棵树全为空 if(p == null && q == null){ return true; } //一棵树为空 if(p == null || q == null){ return false; } //两棵树均不为空 //先判断根节点是否相同 if(p.val != q.val){ return false; } return isSameTree(p.left,q.left) && isSameTree(p.right,q.right); }题目：在线OJ
思考：
判断一棵树是不是另外一棵树的子树，本质就是在判断一棵树和另外一颗树的某个子树是否相等
可使用：遍历 + 递归拆分问题
上述满足一个即可
画图：
上述画了左子树的情况，若左子树在不相同，接着再递归右子树与子树比较，只要符合一种情况即可
代码实现：
public boolean isSubtree(TreeNode root, TreeNode subRoot) { //两棵树都为空 if(root == null && subRoot == null){ return true; } //一棵树为空 if(root == null || subRoot == null){ return false; } boolean ret = false; //根节点的值 相同 if(root.val == subRoot.val){ ret = isSameTree(root,subRoot); } return ret || isSubtree(root.left,subRoot) || isSubtree(root.right,subRoot);}题目：在线OJ
思考：
深度即：根节点到最远叶子节点的层数
此处要注意深度是从 0 开始算，还是从 1 开始算
二叉树的最大深度，即：max(左子树深度，右子树深度) + 1
代码实现：
public int maxDepth(TreeNode root) { //空树 if(root == null){ return 0; } //左右子树为空 只有根节点 if(root.left == null && root.right == null){ return 1; } int leftDepth = maxDepth(root.left); int rightDepth = maxDepth(root.right); return 1 + (leftDepth > rightDepth ? leftDepth : rightDepth) ; }题目：在线OJ
思考：
即：一棵树是否平衡，先判断该树自己的左右子树高度差是否 ≤ 1，还要满足左右子树也平衡才可以判断该树是平衡树
画图分析：
代码实现：
public boolean isBalanced(TreeNode root) { //空树 if(root == null){ return true; } //只有根节点 左右子树为空 if(root.left == null && root.right == null){ return true; } //判断当前节点对应的子树是否平衡 int leftDepth = maxDepth(root.left); int rightDepth = maxDepth(root.right); if(leftDepth - rightDepth > 1 || leftDepth - rightDepth < -1){ return false; } return isBalanced(root.left) && isBalanced(root.right);}题目：在线OJ
思考：
判断一棵树是否对称，本质上就是判断该树的所有子树是否对称
画图分析：
代码实现：
public boolean isSymmetric(TreeNode root) { //空树 if(root == null){ return true; } return isMirror(root.left,root.right);}public boolean isMirror(TreeNode t1,TreeNode t2){ //左右子树都为空 if(t1 == null && t2 == null){ return true; } //一棵子树为空 if(t1 == null || t2 == null){ return false; } //两棵树的根节点 值不相等 if(t1.val != t2.val){ return false; } return isMirror(t1.left,t2.right) && isMirror(t1.right,t2.left);}题目：在线OJ
思考：
画图分析：
代码实现：
public class BuildTreeDemo { //静态内部类 static class TreeNode{ public char val; TreeNode left; TreeNode right; public TreeNode(char val) { this.val = val; } } public static void main(String[] args) { Scanner scan = new Scanner(System.in); //循环输入 在线OJ 一般都是多组用例 while(scan.hasNext()){ // s这个字符串就对应一对形如“abc##de#g##f###” 的输入数据 String s = scan.next(); TreeNode root = build(s); //中序遍历 inOrder(root); System.out.println(); } } private static void inOrder(TreeNode root) { //若为空树，直接返回 if(root == null){ return; } //递归访问左子树 inOrder(root.left); //访问根节点 System.out.print(root.val+" "); //递归访问右子树 inOrder(root.right); } // index用来记录访问到 s 的哪个元素 private static int index = 0; private static TreeNode build(String s) { index = 0; //先序遍历 return createTreePrevOrder(s); } private static TreeNode createTreePrevOrder(String s) { //获取到当前处理到哪个节点 char cur = s.charAt(index); if(cur == "#"){ return null; } TreeNode root = new TreeNode(cur); index++; //下一个节点开始就是当前root左子树的先序遍历结果 root.left = createTreePrevOrder(s); index++; root.right = createTreePrevOrder(s); return root; }}部分递归过程分析：
题目：在线OJ
思考：
创建一个变量 result 来存放我们的结果，最后 return result
(result 相当于一个二维数组，result 0 对应第0层节点，result 1 对应第1层节点…)
代码实现：
static List<List<Integer>> result = new ArrayList<>();public List<List<Integer>> levelOrder(TreeNode root) { //清空result 因为result是全局变量 result.clear(); //空树判定 if(root == null){ return null; } // helper 方法辅助递归，第二个参数表示当前层数 从 0 开始算 helper(root,0); return result;}private void helper(TreeNode root, int level) { if(level == result.size()){ result.add(new ArrayList<>()); } //把当前节点添加到 result 中的合适位置 result.get(level).add(root.val); if(root.left != null){ helper(root.left,level + 1); } if(root.right != null){ helper(root.right,level + 1); }}代码分析：
思考：
代码实现：
public List<List<Integer>> levelOrder(TreeNode root){ //创建一个 result 来存放结果 List<List<Integer>> result = new ArrayList<>(); //空树判断 if(root == null){ return result; } //创建一个队列，把根节点加入队列 Queue<TreeNode> queue = new LinkedList<>(); queue.add(root); //队列不为空，就一直循环 while ( !queue.isEmpty()){ //定义为一个 list 来存放每一层节点 List<Integer> list = new ArrayList<>(); //队列中当前所存在的数 即为当前层所有的数 int level = queue.size(); for (int i = 0; i < level; i++) { // 获得并将第一个节点出队列 TreeNode cur = queue.poll(); list.add(cur.val); if(cur.left != null){ queue.add(cur.left); } if(cur.right != null){ queue.add(cur.right); } } result.add(list); } return result;}题目：在线OJ
思考：
若从某个节点开始，后续遍历能把 p 和 q 都找到，说明该节点就是 p 和 q 的公共祖先
若从某个节点开始，后续遍历能把 p 和 q 都找到，并且 p 和 q 不在同一子树中，则当前节点就是 p 和 q 的最近公共祖先
代码实现：
private TreeNode lca = null;public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) { //空树判断 if(root == null){ return null; } // findNode方法，在递归寻找的过程中，找到结果，就将结果放到 lca 中 findNode(root,p,q); //返回 lca return lca;}//从 root 出发找 p q,只要找到 1 个，就返回true，都找不到返回falseprivate boolean findNode(TreeNode root, TreeNode p, TreeNode q) { //空树判断 if(root == null){ return false; } // 递归 后序遍历查找 int left = findNode(root.left,p,q) ? 1 : 0; int right = findNode(root.right,p,q) ? 1 : 0; int mid = (root == p || root == q) ? 1 : 0; if(left + right + mid == 2){ lca = root; } return (left + right +mid
文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。
转载请注明本文地址：https://www.ucloud.cn/yun/122129.html
摘要：不过幸运的是所有面试的公司都给了，在这里总结下经验吧。这里推荐下我当时看的一篇的面经，木易杨老师写的大厂高级前端面试题汇总。 前言 本人毕业一年，最近陆续面试了头条、瓜子、360、猿辅导、中信银行、老虎等公司，由于最近比较寒冬而且招1-3年的并不多，再加上自己对公司规模和位置有一定要求，所以最后合适的也就这几家了。不过幸运的是所有面试的公司都给了offer，在这里总结下经验吧。掘金：h...
文章目录 1️⃣前言：追忆我的刷题经历2️⃣算法和数据结构的重要性?1、适用人群?2、有何作用?3、算法简介?4、数据结构 3️⃣如何开始持续的刷题?1、立军令状?❤️?2、培养兴趣?3、狂切水题??4、养成习惯?5、一周出师 4️⃣简单数据结构的掌握?1、数组?2、字符串?3、链表?4、哈希表???5、队列????6、栈?7、二叉树?8、多叉树?9、森林?10、树状数组?11、...
摘要：知识点中一般支持以下几种常见的索引树索引全文索引哈希索引我们今天重点来讲下树索引，以及为什么要用树来作为索引的数据结构。平衡二叉树定义首先符合二叉查找树的定义，另外任何节点的两个子树高度最大差为。showImg(https://user-gold-cdn.xitu.io/2019/5/22/16adede6b0fb7489); 前言 讲到索引，第一反应肯定是能提高查询效率。例如书的目录，想要...
摘要：若遇到哈希冲突，则将冲突的值加到链表中即可。之后相比于之前的版本，之后在解决哈希冲突时有了较大的变化，当链表长度大于阈值默认为时，将链表转化为红黑树，以减少搜索时间。有序，唯一红黑树自平衡的排序二叉树。 本文是最最最常见Java面试题总结系列第三周的文章。主要内容： Arraylist 与 LinkedList 异同 ArrayList 与 Vector 区别 HashMap的底层...
摘要：月下半旬攻略道题，目前已攻略题。目前简单难度攻略已经到题，所以后面会调整自己，在刷算法与数据结构的同时，攻略中等难度的题目。 Create by jsliang on 2019-07-30 16:15:37 Recently revised in 2019-07-30 17:04:20 7 月下半旬攻略 45 道题，目前已攻略 100 题。 一 目录 不折腾的前端，和咸鱼有什么区别...
阅读 462·2021-11-15 11:37
阅读 3384·2021-10-11 10:58
阅读 3752·2021-09-09 09:34
阅读 3416·2019-08-30 15:52
阅读 2454·2019-08-29 14:03
阅读 2703·2019-08-26 13:36
阅读 1462·2019-08-26 12:16
阅读 1489·2019-08-26 11:45
