之前去面试，被问到了一个关于二叉树的问题，本身对算法并不擅长，结果想了半天没想出解决方法，经过面试官提点，才恍然大悟，回来后立马把实现写了出来，详见如下。...面试题 题目是这样的，有一个二叉树如下，然后按深度进行打印，应该是1,2,3,4,5,6,7 。 ?...这个一下就能想到是递归，没问题，啪啪啪实现了一通，结果实现出来真实打印出来的却是：1,2,4,5,3,6,7，就实现失败了。...后来面试官说将每层的元素都存储起来再递归，回来想了一下就将实现写了出来，详见如下。 代码实现 Node节点类 很简单，没什么好说的。...总结 对于二叉树的面试题，一般情况下，都是离不开递归，再想想，每次递归的角色是什么，像我这道题的角色就是每层节点，因为需要按层去打印数据。如果定位到递归角色，再想实现逻辑就好多了。
题目描述 从上往下打印出二叉树的每个节点，同层节点从左至右打印。...import java.util.ArrayList; import java.util.Queue; import java.util.LinkedList; /** public class TreeNode
大家好，又见面了，我是你们的朋友全栈君。 层序遍历的思路：若树为空，则返回空，否则从树的第一层开始，即从根节点，从上而下逐层遍历。 1....二叉树层序遍历Ⅰ——剑指offer32-Ⅰ 从上到下，从左到右打印二叉树，返回一维数组int[] res。...二叉树层序遍历Ⅱ——剑指offer32-Ⅱ/LeetCode102 从上到下，从左到右打印二叉树，返回List> res。...二叉树层序遍历Ⅲ——剑指offer32-Ⅲ/LeetCode103 从上到下，按zigzag方式打印(即先从左往右，再从右往左进行下一层遍历，以此类推，层与层之间交替进行)，返回List> res。...二叉树层序遍历Ⅳ——LeetCode107 从下到上，从左到右打印二叉树，返回List> res。
一.前言 我们需要先构建个二叉树，方便后续对函数的测试； 还有我们在实现二叉树的这些函数时，尽量少用遍历，这里用的比较多的就是递归和分治思想。...0 : TreeSize(root->left) + TreeSize(root->right) + 1; } 二.二叉树的深度 还是利用分治的思想； 1.分别算出左子树和右子树的深度； 2.然后比较二者的大小...，大的返回； 3.不要忘了+1,因为根节点也算是一个深度。...left + 1 : right + 1; } 三.二叉树第k层的节点数 二叉树第k层的节点数=左子树的第k-1层的节点数+右子树第k-1层的节点数。....二叉树叶节点的个数 叶节点就是没有子节点的节点，我们可以分别记录下当前节点的左节点和右节点，如果都为空，那么叶节点的个数+1。
查找二叉树子节点的最近共同父节点 分析 实现 算法复杂度 其他算法 题目升级 给定一个二叉搜索树, 找到该树中两个指定节点的最近公共祖先。...百度百科中最近公共祖先的定义为：“对于有根树 T 的两个结点 p、q，最近公共祖先表示为一个结点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。”...分析 对于二叉树来讲，由于左右子树指针的存在，使得正常情况下的自上而下遍历显得比较简单，而下而上的查找并不那么容易，所以一种直观的思维就是从根节点开始遍历，直到找到节点p pp，记录路径数组为p a t...题目升级 如果题目中的树只是一颗普通的二叉树，那么最近父节点该怎么查找？...left : right; } 同样最坏的情况是，二叉树退化成了一个类似于单链表的结构,p,q两个节点就在表的末端最后两个节点，这样的话，时间复杂度也会变为O ( n ) O(n)O(n);不消耗额外的空间
这里强调一波概念： 二叉树节点的深度：指从根节点到该节点的最长简单路径边的条数。 二叉树节点的高度：指从该节点到叶子节点的最长简单路径边的条数。...但leetcode中强调的深度和高度很明显是按照节点来计算的，如图： 关于根节点的深度究竟是1 还是 0，不同的地方有不一样的标准，leetcode的题目中都是以节点为一度，即根节点深度是1。...因为求深度可以从上到下去查 所以需要前序遍历（中左右），而高度只能从下到上去查，所以只能后序遍历（左右中） 有的同学一定疑惑，为什么104.二叉树的最大深度中求的是二叉树的最大深度，也用的是后序遍历。...那是因为代码的逻辑其实是求的根节点的高度，而根节点的高度就是这颗树的最大深度，所以才可以使用后序遍历。...这个函数通过栈模拟的后序遍历找每一个节点的高度（其实是通过求传入节点为根节点的最大深度来求的高度） 代码如下： // cur节点的最大深度，就是cur的高度 int getDepth(TreeNode*
/** * 二叉树的生成 */ public static ArrayList> PrintFromTopToBottom(TreeNode...node.left = nodes.get(i*2 + 1); node.right = nodes.get(i*2 + 2); } // 只有当总节点数是奇数时...，最后一个父节点才有右子节点 int lastPNodeIndex = arrs.length/2 - 1; TreeNode lastPNode = nodes.get
从根开始定义起，根为第1层，根的子节点为第2层，以此类推； 树的高度或深度：树中节点的最大层次； 如上图：树的高度为4 关于树的高度，还有一种看法，就是把高度从0开始看，此时树的高度为3。...对 于深度为K的，有n个结点的二叉树，当且仅当其每一个结点都与深度为K的满二叉树中编号 从1至n的结点一一对应时称之为完全二叉树。 要注意的是满二叉树是一种特殊的完全二叉 树。...若规定根节点的层数为1，则一棵非空二叉树的第i层上最多有2^(i-1) 个结点. 2. 若规定根节点的层数为1，则深度为h的二叉树的最大结点数是2^h- 1. 3....若规定根节点的层数为1，具有n个结点的满二叉树的深度，h=logN + 1 2.51 顺序存储： 顺序结构存储就是使用数组来存储，一般使用数组只适合表示完全二叉树，因为不是完全二叉树 会有空间的浪费...} 4.4前序，中序，后序(深度优先遍历) // 先序遍历二叉树 void PrevOrder(BTNode* root) { // 如果当前节点为空，则打印"NULL"并返回 if (root
一个节点也可以没有子节点，这时该节点就是叶子节点（leaf node）。 二叉树有许多不同的类型，其中比较常见的包括二叉搜索树、平衡二叉树、红黑树等。...二叉树的创建和嵌套打印 首先用一个类来封装二叉树的节点 public class TreeNode { int data;//数据 TreeNode left;//左子节点 TreeNode...二叉树的遍历是指按照一定的顺序访问树中的每个节点。...= null) { queue.offer(head.right); } } } 二叉树的深度和叶子节点的个数 public...int treeDepth(TreeNode root) {//求二叉树的深度 if (root == null) return 0; return Math.max(
读完本文，和二叉树打印相关的题目你都可以拿下，由于本文图片很多，建议在 WIFI 环境下阅读。...首先是第一道，从上到下打印出二叉树的每个节点，同一层的节点按照从左到右的顺序打印，比如给定二叉树 [3,9,20,null,null,15,7]。 ? 返回 [3,9,20,15,7]。...：请实现一个函数按照之字形顺序打印二叉树，即第一行按照从左到右的顺序打印，第二层按照从右到左的顺序打印，第三行再按照从左到右的顺序打印，其他行以此类推。...(temp); } // 返回 res return res; } } 今天的内容就是这些，总的来说，关于二叉树打印的这三道算法题在整体的思考方向上都是一致的...，都需要借助辅助结构队列用来临时存储二叉树中的节点元素，然后再按照题目的要求进行输出。
二、题目描述： 题目： 给定一个二叉树，找出其最小深度。 最小深度是从根节点到最近叶子节点的最短路径上的节点数量。 说明：叶子节点是指没有子节点的节点。... [0, 105] 内 -1000 <= Node.val <= 1000 题目来源： LeetCode官网题目难度：⭐⭐ 三、思路分析： 题目给定：最小深度是从根节点到最近叶子节点的最短路径上的节点数量...凡是遇到二叉树题，递归也是我最能想到的，哈哈哈，但是还是存在很大的优化空间的，比如深度优先搜索或者广度优先搜索。具体思路及解题步骤请看如下： 当前节点 root 为空时，说明此处树的高度为 0。...如果为其他情况，则说明当前节点有值，且需要分别计算其左右子树的最小深度，返回最小深度进行+1，+1 表示当前节点存在有 1 个深度。...，则分别计算左右节点的最小深度。
二、题目描述： 题目： 给定一个二叉树，找出其最大深度。 二叉树的深度为根节点到最远叶子节点的最长路径上的节点数。 说明: 叶子节点是指没有子节点的节点。...二叉树的深度是从根节点开始算起，依次往下是深度 1、2、3...n。你就可以理解成一口井，从上往下看，也就是自顶向下看。...(root.right); // 二叉树的最大深度 = 子树的最大深度 + 1（因为1是根节点；这点别忘了） return Math.max(leftHeight..., rightHeight) + 1; } } 五、总结： 递归法之leetcode提交运行结果截图如下： 复杂度分析： 时间复杂度：O(n)，其中 n 为二叉树节点的个数。...每个节点在递归中只被遍历一次。 空间复杂度：O(height)，其中height 表示二叉树的高度。递归函数需要栈空间，而栈空间取决于递归的深度，因此空间复杂度等价于二叉树的高度。
大家好，又见面了，我是你们的朋友全栈君。...递归获取所有子节点测试用例： /** * 获取子级ids，含自己 * @param id 父节点 * @param TaxBureauList 组织单位列表 *...Object>> TaxBureauList) { for (Map bureau : TaxBureauList) { //过滤父节点为空的数据...MapUtils.getString(bureau,"parentId",""))){ continue; } // 判断是否存在子节点...如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 举报，一经查实，本站将立刻删除。
题目 二叉树中找到一个节点的后继节点，前继节点 现在有一种新的二叉树节点类型如下： public static class Node { public Node left; public...Node parent; public int value; public Node(int data) { value = data; } } 该结构比普通二叉树节点结构多了一个指向父节点...假设有一 棵Node类型的节点组成的二叉树，树中每个节点的parent指针都正确地指向自己的父节点，头节点的parent指向null。...只给一个在二叉树中的某个节点 node，分别实现返回node的后继，前继节点的函数。 在二叉树的中序遍历的序列中，node的下一个节点叫作node的后继节点，node的上一个节点叫做前节点。...// 因为中序遍历的过程是：左中右，因此打印完当前节点（zhong），下一个节点就是右 // 然后下一个递归过程又是左中右，因此后继节点必然是右子树中，最左边的节点 if (node.right
array = {1, 2, 3, 4, 5}; for (int a : array) { System.out.println(a); } } 利用Array类中的toString...()方法 调用时传入要遍历打印的数组返回一个包含数组元素的字符串，这些元素被放置在括号内，并用逗号分开 @Test public void test() { int[] array = {1,
【题目】现在有一种新的二叉树节点类型如下： public class Node { public int value; public Node left;...public Node parent; public Node(int data) { this.value = data; } } 该结构比普通二叉树节点结构多了一个指向父节点的...假设有一棵该Node类型的节点组成的二叉树，树中每个节点的parent指针 都正确地指向自己的父节点，头节点的parent指向null。...只给一个在二叉树中的某个节点 node，请实现返回node的后继节点的函数。 在二叉树的中序遍历的序列中， node的下一个节点叫作node的后继节点。node的上一个节点叫作node的钱去节点....第二种方法 :其实一个结点的后继结点有这样一个规律 如果当前结点有右子树,则其后继结点是右子树的最左结点 如果当前结点没有右子树,则从父结点开始向上找,一直到当前结点是其父结点的左孩子时候停,那么当前结点的父结点就是其后继结点
return a; } //求二叉树节点个数 //使用后序遍历 public static int size(Node root){...if (root == null){ return 0; } //访问根节点，此处的访问操作就是计数器+1 //整个树的节点个数...= 根节点个数 + 左子树节点的个数 + 右子树节点个数 return 1 + size(root.left) + size(root.right); } //求二叉树叶子节点的个数...//root叶子节点的个数 = root.left的叶子节点的个数 + root.right叶子节点的个数 public static int leafSize(Node root){...return 1; } return kSize(root.left, k-1)+kSize(root.right, k-1); } //在二叉树中查找指定的元素
题目： 在二叉树中，根节点位于深度 0 处，每个深度为 k 的节点的子节点位于深度 k+1 处。 如果二叉树的两个节点深度相同，但 父节点不同 ，则它们是一对堂兄弟节点。...我们给出了具有唯一值的二叉树的根节点 root ，以及树中两个不同节点的值 x 和 y 。 只有与值 x 和 y 对应的节点是堂兄弟节点时，才返回 true 。否则，返回 false。...null,4,null,5], x = 5, y = 4 输出：true 示例 3： 输入：root = [1,2,3,null,4], x = 2, y = 3 输出：false 分析 这是一道标准的二叉树递归搜索问题...首先，根据题目定义好的TreeNode可以获取到当前节点的值，以及左子树和右子树。 我们初始化传入节点，父节点(root没有父节点，传自身)，以及最大深度（初始为0）。...遍历过程中比较x,y的数值，并记录深度和父节点，当节点不存在返回即可。
在二叉树中找到一个节点的后继节点 现在有一种新的二叉树节点类型如下： public class Node { public int value; public Node left; public Node...right; public Node parent; public Node(int data) { this.value = data; } } 该结构比普通二叉树节点结构多了一个指向父节点的...假设有一 棵Node类型的节点组成的二叉树， 树中每个节点的parent指针都正确地指向自己的父节点， 头节点的parent指向null。...只给一个在二叉树中的某个节点 node， 请实现返回node的后继节点的函数。 在二叉树的中序遍历的序列中， node的下一个节点叫作node的后继节点。
领取专属 10元无门槛券
手把手带您无忧上云
云服务器
ICP备案
腾讯会议
云直播
对象存储
