网站开发的过程步骤,建网站做联盟,傻瓜式做网站,济南网站建设抖音平台#x1f525;博客主页#xff1a; 【小扳_-CSDN博客】 ❤感谢大家点赞#x1f44d;收藏⭐评论✍ 文章目录 1.0 平衡二叉树 1.1 实现判断平衡二叉树的思路 1.2 代码实现判断平衡二叉树 2.0 二叉树的层序遍历 2.1 实现二叉树层序遍历的思路 2.2 代码实现二叉树层序遍历 3.0 … 博客主页 【小扳_-CSDN博客】 ❤感谢大家点赞收藏⭐评论✍ 文章目录 1.0 平衡二叉树 1.1 实现判断平衡二叉树的思路 1.2 代码实现判断平衡二叉树 2.0 二叉树的层序遍历 2.1 实现二叉树层序遍历的思路 2.2 代码实现二叉树层序遍历 3.0 二叉树的最近公共祖先 3.1 实现二叉树的最近公共祖先的思路 3.2 代码实现二叉树的最近公共祖先 4.0 根据二叉树创建字符串 4.1 实现根据二叉树创建字符串的思路 4.2 代码实现根据二叉树创建字符串 1.0 平衡二叉树 题目 给定一个二叉树判断它是否是高度平衡的二叉树。 本题中一棵高度平衡二叉树定义为 一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过 1 。 示例 1 输入root [3,9,20,null,null,15,7]
输出true OJ链接 110. 平衡二叉树 1.1 实现判断平衡二叉树的思路 具体思路为只需要判断当前节点的左右子树最大深度差是否大于 1 即可。利用递归的方式来获取当前节点的最大深度利用该节点的深度与另一个兄弟节点进行比较若差值的绝对值对于 1 时说明不是平衡二叉树。 1.2 代码实现判断平衡二叉树 /*** 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.val val;* this.left left;* this.right right;* }* }*/
class Solution {public boolean isBalanced(TreeNode root) {recursion(root);return sign;}public boolean sign true;public int recursion(TreeNode node) {if(node null) {return 0;}int l recursion(node.left);int r recursion(node.right);if(l r) {int temp l;l r;r temp;}if(l - r 1) {sign false;}return l 1;}
} 2.0 二叉树的层序遍历 给你二叉树的根节点 root 返回其节点值的 层序遍历 。 即逐层地从左到右访问所有节点。 示例 1 输入root [3,9,20,null,null,15,7]
输出[[3],[9,20],[15,7]] OJ链接 102. 二叉树的层序遍历 2.1 实现二叉树层序遍历的思路 具体思路为利用层序遍历来进行按照从上到下从左到右的顺序来访问每一层的节点。 简单分析如何实现层序遍历利用了队列的数据结构的特点先进先出。那么先从根节点出发将其压入队列中接着判断从队列中弹出来的节点的左右孩子若该节点的左孩子不为 null 时将其压入队列中若右孩子不为 null 时将其压入队列中。循环往复循环条件终止条件为当队列为空时说明已经把该树遍历完毕了。 回来再来看需要将不同层级的节点放到不同的容器中那么就可以利用每一层节点的个数来实现将不同的层级的节点放到不同的容器中。简单来说就是当前的层级有多少个节点数然后将这些的节点收集到同一个容器中实现该效果可以利用压入队列中的节点个数为循环条件将其放到同一的容器中。 2.2 代码实现二叉树层序遍历 /*** 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.val val;* this.left left;* this.right right;* }* }*/
class Solution {public ListListInteger levelOrder(TreeNode root) {if(root null) {return new ArrayList();}ListListInteger list new ArrayList();LinkedListTreeNode queue new LinkedList();queue.offer(root);while (!queue.isEmpty()) {ListInteger list1 new ArrayList();int size queue.size();for (int i 0; i size; i) {TreeNode poll queue.poll();if (poll.left ! null) {queue.offer(poll.left);}if (poll.right ! null) {queue.offer(poll.right);}list1.add(poll.val);}list.add(list1);}return list;}
} 3.0 二叉树的最近公共祖先 题目 给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。 百度百科中最近公共祖先的定义为“对于有根树 T 的两个节点 p、q最近公共祖先表示为一个节点 x满足 x 是 p、q 的祖先且 x 的深度尽可能大一个节点也可以是它自己的祖先。” 示例 1 输入root [3,5,1,6,2,0,8,null,null,7,4], p 5, q 1
输出3
解释节点 5 和节点 1 的最近公共祖先是节点 3 。OJ链接: 236. 二叉树的最近公共祖先 3.1 实现二叉树的最近公共祖先的思路 具体思路为一般分为两种情况 第一种p 直接就是 q 的祖先或者 q 直接就是 p 的祖先。 示例 2 输入root [3,5,1,6,2,0,8,null,null,7,4], p 5, q 4
输出5
解释节点 5 和节点 4 的最近公共祖先是节点 5 。因为根据定义最近公共祖先节点可以为节点本身。 这属于是第一种情况节点 5 就是节点 4 的最近公共祖先。因此节点 5 必定在节点 4 之前所以只要遍历找到节点 5 就可以直接返回该节点不需要再遍历下去了。当且仅当一个节点不为 null 另一个节点为 null 时肯定属于第一种情况。 第二种互不为对方的祖先。 示例 1 输入root [3,5,1,6,2,0,8,null,null,7,4], p 5, q 1
输出3
解释节点 5 和节点 1 的最近公共祖先是节点 3 。 这属于第二种情况互不为对方的祖先。这也简单只要通过递归来找到当前根节点的左右节点为 q 或者 p 或者在当前的根节点中左右子树中可以找到的 q 或者 p 时那么说明 q 与 p 同时都不为 null 时当前的根节点就是他们最近的祖先节点。这就是属于第二种情况。 3.2 代码实现二叉树的最近公共祖先 /*** Definition for a binary tree node.* public class TreeNode {* int val;* TreeNode left;* TreeNode right;* TreeNode(int x) { val x; }* }*/
class Solution {public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {if(root p || root null || root q) {return root;}TreeNode left lowestCommonAncestor(root.left,p,q);TreeNode right lowestCommonAncestor(root.right,p,q);if(left ! null right ! null) {return root;}return (left ! null ? left : right);}
} 4.0 根据二叉树创建字符串 题目 给你二叉树的根节点 root 请你采用前序遍历的方式将二叉树转化为一个由括号和整数组成的字符串返回构造出的字符串。 空节点使用一对空括号对 () 表示转化后需要省略所有不影响字符串与原始二叉树之间的一对一映射关系的空括号对。 示例 1 输入root [1,2,3,4]
输出1(2(4))(3)
解释初步转化后得到 1(2(4)())(3()()) 但省略所有不必要的空括号对后字符串应该是1(2(4))(3) 。 OJ链接 606. 根据二叉树创建字符串 4.1 实现根据二叉树创建字符串的思路 具体思路为利用前序遍历得到的每一个节点的值拼接到可变字符串中在拼接之前需要加上左括号根节点开始从左子树遍历若左子树遍历完需要原路返回判断当前节点的右子树有无节点若有节点则发生的是子问题过程了若没有节点了最后需要在可变中字符串拼接上右括号。 4.2 代码实现根据二叉树创建字符串 /*** 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.val val;* this.left left;* this.right right;* }* }*/
class Solution {public String tree2str(TreeNode root) {recursion(root);return string.substring(1,string.length()-1);}public StringBuilder string new StringBuilder();public void recursion(TreeNode node) {string.append(();string.append(node.val);if (node.left ! null) {recursion(node.left);}else if(node.right ! null) {string.append(());}if (node.right ! null) {recursion(node.right);}string.append());}
}
