题目描述 给定一个二叉树，判断它是否是高度平衡的二叉树。 本题中，一棵高度平衡二叉树定义为： 一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过 1 。 平衡二叉树 解题思路 首先我们从根节点出发，要是它的左子树的高度和右子树的高度差距大于1，那么就返回false，不是的话就依次往下遍历，比如，遍历树的左子树，递归的方式，将整个树遍历完成。这里还需要写一个求树高度的方法，方便调用。 代码展示 class Solution {...
题目描述 给定一个二叉树，找出其最大深度。 二叉树的深度为根节点到最远叶子节点的最长路径上的节点数。 说明: 叶子节点是指没有子节点的节点。 示例： 给定二叉树 [3,9,20,null,null,15,7]， 3/ 9 20/ 15 7返回它的最大深度 3 。 题解 方法1：层序遍历 有几层深度就是多少，做过层序遍历的都懂public int maxDepth(TreeNode root) {Queue<TreeNode> queue = new LinkedList<>();int maxDept=0;if (root==null){return m...
根据一棵树的前序遍历与中序遍历构造二叉树。 思路： 1.根据前序数组，找到根节点 2.根据中序数组中的根节点，找到左子树的长度 3.根据左子树的长度，找到左右子树的前序数组和中序数组 4.递归调用，直到前序数组为null function TreeNode(val, left, right) {this.val = (val===undefined ? 0 : val)this.left = (left===undefined ? null : left)this.right = (right===undefined ? null : right) } var buildTree = function(pr...
若设二叉树的深度为 h，除第 h 层外，其它各层 (1～h-1) 的结点数都达到最大个数，第 h 层所有的结点都连续集中在最左边，这就是完全二叉树。（注：第 h 层可能包含 1~ 2h 个节点。） 示例 1： 输入：[1,2,3,4,5,6]输出：true解释：最后一层前的每一层都是满的（即，结点值为 {1} 和 {2,3} 的两层），且最后一层中的所有结点（{4,5,6}）都尽可能地向左。示例 2：输入：[1,2,3,4,5,null,7]输出：false解释：值为 7 的结点没有尽...
1 // 主函数2 Node connect(Node root) {3 //--主函数可以解决：4 //--用递归函数遍历左右节点时，5 //--root节点必定是完全没有兄弟节点的特殊情况，6 //--将root节点独立处理7 if (root == null) return null;8 connectTwoNode(root.left, root.right);9 return root; 10 } 11 12 // 辅助函数 13 //--辅助函数即递归函数的主体 14 void connectTwoNode(Node node1, Node node2) { 15 //--二叉树...
给你二叉树的根结点 root ，请你将它展开为一个单链表： 展开后的单链表应该同样使用 TreeNode ，其中 right 子指针指向链表中下一个结点，而左子指针始终为 null 。 展开后的单链表应该与二叉树 先序遍历 顺序相同。 示例 1： 输入：root = [1,2,5,3,4,null,6] 输出：[1,null,2,null,3,null,4,null,5,null,6] 示例 2： 输入：root = [] 输出：[] 示例 3： 输入：root = [0] 输出：[0] 提示： 树中结点数在范围 [0, 2000] 内 -100...
根据一棵树的前序遍历与中序遍历构造二叉树。 注意: 你可以假设树中没有重复的元素。 例如，给出 前序遍历 preorder = [3,9,20,15,7] 中序遍历 inorder = [9,3,15,20,7] 返回如下的二叉树：思路：这道题用递归来解决。 首先我们能从一个树的前序遍历序列得知该树的根节点的值。然后我们去中序遍历序列里面找根节点所在位置，那么根节点左右两侧的子序列就是左子树和右子树的中序序列。然后我们再去前序序列里面找，根节点之后紧跟的...
二叉树的层序遍历II 题目描述： 给定一个二叉树，返回其节点值自底向上的层序遍历。 （即按从叶子节点所在层到根节点所在的层，逐层从左向右遍历） 题目链接 /*** Definition for a binary tree node.* public class TreeNode {* int val;* TreeNode left;* TreeNode right;* TreeNode() {}* TreeNode(int val) { this.val = val; }* TreeNode(int val, TreeNode left, TreeNode right) {* this.v...
# Definition for a binary tree node. # class TreeNode: # def __init__(self, x): # self.val = x # self.left = None # self.right = Noneclass Solution:def isSymmetric(self, root: TreeNode) -> bool:def recur(L,R):# 如果左右树都为空，则为遍历完的情况，返回Trueif not L and not R:return True# 一个为空一个不为空或者当前的值不同，返回Falseif not L or not R or L.val!=R.val:return...
331. 验证二叉树的前序序列化 题目地址 描述序列化二叉树的一种方法是使用前序遍历。当我们遇到一个非空节点时，我们可以记录下这个节点的值。如果它是一个空节点，我们可以使用一个标记值记录，例如 #。例如，上面的二叉树可以被序列化为字符串 "9,3,4,#,#,1,#,#,2,#,6,#,#"，其中 # 代表一个空节点。 给定一串以逗号分隔的序列，验证它是否是正确的二叉树的前序序列化。编写一个在不重构树的条件下的可行算法。 每个以逗号分隔的...
Leetcode 102. 二叉树的层序遍历 题目描述：给你一个二叉树，请你返回其按 层序遍历 得到的节点值。 （即逐层地，从左到右访问所有节点）。 一道非常标准的宽度优先搜索题目，直接套算法模板就成。 /*** Definition for a binary tree node.* struct TreeNode {* int val;* TreeNode *left;* TreeNode *right;* TreeNode() : val(0), left(nullptr), right(nullptr) {}* TreeNode(int x) : val(x), left(null...
题目 递归保存当前结点的左右结点，遇到的左结点直接拼到右节点，左节点遍历完之后回溯，找到当前最底层的右结点，再将右节点拼接过去。两个版本 一 有返回值public TreeNode build(TreeNode root){if (root == null) return null;TreeNode left = root.left;TreeNode right = root.right;root.left = null;root.right = build(left);TreeNode tmp = root;while (tmp.right != null) tmp = tmp.right;tmp.right = build(right);re...
题目描述 给定一个二叉树，找出其最小深度。 最小深度是从根节点到最近叶子节点的最短路径上的节点数量。 说明：叶子节点是指没有子节点的节点。 示例 1： 输入：root = [3,9,20,null,null,15,7]输出：2 示例 2： 输入：root = [2,null,3,null,4,null,5,null,6]输出：5 dfs遍历 bfs遍历 参考： https://leetcode-cn.com/problems/minimum-depth-of-binary-tree
本文是记录做该类题的一些思想，效率不算特别高，只是提供一些新的想法； 在LeetCode的剑指offer篇章中，有三个特别近似的打印二叉树的题目，分别是： (1)剑指Offer 32 - I 从上到下打印二叉树 (2)剑指 Offer 32 - II 从上到下打印二叉树 II (3)剑指 Offer 32 - III 从上到下打印二叉树 III 三道其实都是BFS； 第一道可以通过创建一个队列实现，利用队列的FIFO实现，将结点从队列取出后，如果子节点非空，就将其子节点放入队列尾...