二叉树

完全二叉树的节点个数一、题目222. 完全二叉树的节点个数 给你一棵 完全二叉树 的根节点 root ，求出该树的节点个数。 完全二叉树 的定义如下：在完全二叉树中，除了最底层节点可能没填满外，其余每层节点数都达到最大值，并且最下面一层的节点都集中在该层最左边的若干位置。若最底层为第 h 层，则该层包含 1~ 2h 个节点。 示例 1： 输入：root = [1,2,3,4,5,6]输出：6 示例 2： 输入：root = []输出：0 示例 3： 输入：root = [1]输出：1 提示： 树中节点的数目范围是[0, 5 * 104] 0 <= Node.val <= 5 * 104 题目数据保证输入的树是 完全二叉树 进阶：遍历树来统计节点是一种时间复杂度为 O(n) 的简单解决方案。你可以设计一个更快的算法吗？ 题解题解一（递归）123456789101112131415161718192021222324252627282930313233/** * Definition for a binary tree node. * public ...

对称二叉树一、题目101. 对称二叉树 给你一个二叉树的根节点 root ， 检查它是否轴对称。 示例 1： 输入：root = [1,2,2,3,4,4,3]输出：true 示例 2： 输入：root = [1,2,2,null,3,null,3]输出：false 提示： 树中节点数目在范围 [1, 1000] 内 -100 <= Node.val <= 100 进阶：你可以运用递归和迭代两种方法解决这个问题吗？ 二、题解题解一（翻转+判断）推荐面试经典-翻转二叉树 面试经典-相同的树 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode ri...

二叉树1234567891011121314151617181920212223public class TreeNode { int val; TreeNode left; TreeNode right; TreeNode() {} TreeNode(int val) { this.val = val; } TreeNode(int val, TreeNode left, TreeNode right) { this.val = val; this.left = left; this.right = right; } public static TreeNode createTree(){ TreeNode root = new TreeNode(1); root.left = new TreeNode(2); root.left.left ...

翻转二叉树一、题目226. 翻转二叉树 给你一棵二叉树的根节点 root ，翻转这棵二叉树，并返回其根节点。 示例 1： 输入：root = [4,2,7,1,3,6,9]输出：[4,7,2,9,6,3,1] 示例 2： 输入：root = [2,1,3]输出：[2,3,1] 示例 3： 输入：root = []输出：[] 提示： 树中节点数目范围在 [0, 100] 内 -100 <= Node.val <= 100 二、题解题解一（广度优先）1234567891011121314151617181920public static TreeNode invertTreeFromBFS(TreeNode root) { if (root == null || (root.left == null && root.right == null)) { return root; } Queue<TreeNode> queue = new LinkedList&l...

相同的树一、题目100. 相同的树 给你两棵二叉树的根节点 p 和 q ，编写一个函数来检验这两棵树是否相同。 如果两个树在结构上相同，并且节点具有相同的值，则认为它们是相同的。 示例 1： 输入：p = [1,2,3], q = [1,2,3]输出：true 示例 2： 输入：p = [1,2], q = [1,null,2]输出：false 示例 3： 输入：p = [1,2,1], q = [1,1,2]输出：false 提示： 两棵树上的节点数目都在范围 [0, 100] 内 -104 <= Node.val <= 104 二、题解 思路： ​ 相同的二叉树，也就是说，两节点，以及两节点的值，都要相同 如果两节点节点相同，即 同为null 捉着同不为 null 同时，值也要相同 ，此时才能说此节点相同 题解一（广度优先）12345678910111213141516171819202122232425262728// 广度优先public static boolean isSameTree(TreeNode p, TreeNod...

二叉树最大深度一、题目104. 二叉树的最大深度 给定一个二叉树 root ，返回其最大深度。 二叉树的 最大深度 是指从根节点到最远叶子节点的最长路径上的节点数。 示例 1： 输入：root = [3,9,20,null,null,15,7]输出：3 示例 2： 输入：root = [1,null,2]输出：2 提示： 树中节点的数量在 [0, 104] 区间内。 -100 <= Node.val <= 100 二、题解 深度优先遍历（Depth-First Search, DFS）是一种常用的树或图的遍历算法。它从根节点开始，沿着树的深度方向遍历节点，尽可能深入地访问每个分支，直到无法继续深入为止，然后回溯到上一个节点，继续访问其他未访问的分支 深度优先遍历（Depth-First Search, DFS）包括前序遍历、中序遍历和后序遍历： 前序遍历（根节点 -> 左子树 -> 右子树）的结果为： 1 -> 2 -> 4 -> 5 -> 3 -> 6 -> 7 中序遍...