合肥网站建设开发电话,汉中建设工程招标网最新公告,深圳市启创网络科技有限公司,哪些网站可以接生意做TOC 前言 代码随想录算法训练营day15 一、Leetcode 102.层序遍历 1.题目 给你二叉树的根节点 root #xff0c;返回其节点值的 层序遍历 。 (即逐层地#xff0c;从左到右访问所有节点)。 示例 1#xff1a; 输入#xff1a;root [3,9,20,null,null,15,7] 输出#xff1a… TOC 前言 代码随想录算法训练营day15 一、Leetcode 102.层序遍历 1.题目 给你二叉树的根节点 root 返回其节点值的 层序遍历 。 (即逐层地从左到右访问所有节点)。 示例 1 输入root [3,9,20,null,null,15,7] 输出[[3],[9,20],[15,7]] 示例 2 输入root [1] 输出[[1]] 示例 3 输入root [] 输出[] 来源力扣(LeetCode) 链接https://leetcode.cn/problems/binary-tree-level-order-traversal 2.解题思路 方法一广度优先搜索 思路和算法 我们可以用广度优先搜索解决这个问题。 我们可以想到最朴素的方法是用一个二元组 (node, level) 来表示状态它表示某个节点和它所在的层数每个新进队列的节点的 level 值都是父亲节点的 level 值加一。最后根据每个点的 level 对点进行分类分类的时候我们可以利用哈希表维护一个以 level 为键对应节点值组成的数组为值广度优先搜索结束以后按键 level 从小到大取出所有值组成答案返回即可。 考虑如何优化空间开销如何不用哈希映射并且只用一个变量 node 表示状态实现这个功能呢 我们可以用一种巧妙的方法修改广度优先搜索 首先根元素入队
当队列不为空的时候求当前队列的长度 sisi依次从队列中取 sisi 个元素进行拓展然后进入下一次迭代 它和普通广度优先搜索的区别在于普通广度优先搜索每次只取一个元素拓展而这里每次取 sisi 个元素。在上述过程中的第 ii 次迭代就得到了二叉树的第 ii 层的 sisi 个元素。 为什么这么做是对的呢我们观察这个算法可以归纳出这样的循环不变式第 ii 次迭代前队列中的所有元素就是第 ii 层的所有元素并且按照从左向右的顺序排列。证明它的三条性质(你也可以把它理解成数学归纳法) 初始化i1i1 的时候队列里面只有 root是唯一的层数为 11 的元素因为只有一个元素所以也显然满足「从左向右排列」
保持如果 ikik 时性质成立即第 kk 轮中出队 sksk 的元素是第 kk 层的所有元素并且顺序从左到右。因为对树进行广度优先搜索的时候由低 kk 层的点拓展出的点一定也只能是 k1k1 层的点并且 k1k1 层的点只能由第 kk 层的点拓展到所以由这 sksk 个点能拓展到下一层所有的 sk1sk1 个点。又因为队列的先进先出(FIFO)特性既然第 kk 层的点的出队顺序是从左向右那么第 k1k1 层也一定是从左向右。至此我们已经可以通过数学归纳法证明循环不变式的正确性。
终止因为该循环不变式是正确的所以按照这个方法迭代之后每次迭代得到的也就是当前层的层次遍历结果。至此我们证明了算法是正确的。 3.代码实现 java class Solution { public List levelOrder(TreeNode root) { List ret new ArrayList(); if (root null) { return ret; } QueueTreeNode queue new LinkedListTreeNode();queue.offer(root);while (!queue.isEmpty()) {ListInteger level new ArrayListInteger();int currentLevelSize queue.size();for (int i 1; i currentLevelSize; i) {TreeNode node queue.poll();level.add(node.val);if (node.left ! null) {queue.offer(node.left);}if (node.right ! null) {queue.offer(node.right);}}ret.add(level);}return ret;
} } 二、Leetcode 226.翻转二叉树 1.题目 给你一棵二叉树的根节点 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 来源力扣(LeetCode) 链接https://leetcode.cn/problems/invert-binary-tree 2.解题思路 方法一递归 这是一道很经典的二叉树问题。显然我们从根节点开始递归地对树进行遍历并从叶子节点先开始翻转。如果当前遍历到的节点 rootroot 的左右两棵子树都已经翻转那么我们只需要交换两棵子树的位置即可完成以 rootroot 为根节点的整棵子树的翻转。 3.代码实现 java class Solution { public TreeNode invertTree(TreeNode root) { if (root null) { return null; } TreeNode left invertTree(root.left); TreeNode right invertTree(root.right); root.left right; root.right left; return root; } } 三、Leetcode 101.对称二叉树 1.题目 给你一个二叉树的根节点 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 来源力扣(LeetCode) 链接https://leetcode.cn/problems/symmetric-tree 2.解题思路 方法一递归 思路和算法 如果一个树的左子树与右子树镜像对称那么这个树是对称的。 fig1 因此该问题可以转化为两个树在什么情况下互为镜像 如果同时满足下面的条件两个树互为镜像 它们的两个根结点具有相同的值
每个树的右子树都与另一个树的左子树镜像对称 fig2 我们可以实现这样一个递归函数通过「同步移动」两个指针的方法来遍历这棵树pp 指针和 qq 指针一开始都指向这棵树的根随后 pp 右移时qq 左移pp 左移时qq 右移。每次检查当前 pp 和 qq 节点的值是否相等如果相等再判断左右子树是否对称。 3.代码实现 java class Solution { public boolean isSymmetric(TreeNode root) { return check(root, root); } public boolean check(TreeNode p, TreeNode q) {if (p null q null) {return true;}if (p null || q null) {return false;}return p.val q.val check(p.left, q.right) check(p.right, q.left);
} }
