上周通过一位小伙伴,加入了一个氛围很好的小群,人不多,但是大家保持着对知识的渴望,让我很感动。 我自己也有一个群,人数也不多,但是能真正互动起来一起学习,一起进步的,还是太少。所以,现在也在学习如何让自己成为更好的群主,带动群活跃,带动一个社群活跃,带动小伙伴们一起进步,是我的愿景。当然,也不否认现在很多群友正在朝着积极向上的方向走着,我要做的,也是时刻保持对知识的渴望,做到“持续学习”。 谁让咱是一名优秀的程序员呢。上周日也学习了一遍递归,还通过一个二叉树的例子来简单介绍了下。我之前解决二叉树相关的问题,基本上用的都是递归,结果那天分享的朋友用了队列,让我眼前一亮,原来程序的世界真是奇妙。 所以,思想碰撞真的是一件很开心的事情。大家在持续的学习,持续的交流中,会打开一些思维定式,接纳更多的方式,你们觉得呢? Algorithm LeetCode算法 https:///problems/flatten-binary-tree-to-linked-list/(https:///problems/flatten-binary-tree-to-linked-list/) 题目描述:给定一个二叉树,原地将它展开为链表。 例如,给定二叉树 示例1: 1 / \2 5/ \ \3 4 6 将其展开为: 1 \ 2 \ 3 \ 4 \ 5 \ 6 本文题解参考地址:https:///problems/flatten-binary-tree-to-linked-list/solution/xiang-xi-tong-su-de-si-lu-fen-xi-duo-jie-fa-by--26/ 解法:后序遍历法 题目其实就是将二叉树通过右指针,组成一个链表。 从例子上可以看出,其实就是让我们把二叉树,通过先序遍历展示出来。所以我们首先想到的是能不能用先序遍历的方式,每遍历一个节点,就将上一个节点的右指针更新为当前节点。 先序遍历的顺序是 1->2->3->4->5->6,如下: 遍历到2,把1的右指针指向2,即变成 1->2 3 4 5 6 遍历到3,把2的右指针指向3,即变成 1->2->3 4 5 6 理想状况下,以此类推即可。 但是,如果我们把1的右指针指向2,那么这时候1原本的右节点就丢失了,也就是我们后续找不到5这个节点。 所以,又引起了我们的思考,如何才能不让5丢失呢?后序遍历可以吗? 也就是我们依次遍历6 5 4 3 2 1,然后每遍历一个节点就将当前节点的右指针更新为上一个节点,如下: 遍历到5,把5的右指针指向6,即变成6 <- 5 4 3 2 1 遍历到4,把4的右指针指向5,即变成6 <- 5 <- 4 3 2 1 以此类推,因为我们更新当前右指针的时候,当前节点的右节点已经访问过了,所以就不会存在丢失节点的问题。 把这个转变成后序遍历,遍历顺序就是 右子树 -> 左子树 -> 根节点 // 将二叉树构建完成public static void main(String[] args) { TreeNode treeNode = new TreeNode(1); treeNode.left = new TreeNode(2); treeNode.left.left = new TreeNode(3); treeNode.left.right = new TreeNode(4); treeNode.right = new TreeNode(5); treeNode.right.right = new TreeNode(6); flattern(treeNode);} /** * * @Title : * @Description: 后续遍历 * @param treeNode * @return :void * @throws */public static void flattern(TreeNode root) { Stack<TreeNode> treeNodes = new Stack<>(); TreeNode current = root; TreeNode preview = null; while (current != null || !treeNodes.isEmpty()) { while (current != null) { // 添加根节点 treeNodes.push(current); // 添加右节点 current = current.right; } // 已经访问到最右边的节点 current = treeNodes.peek(); // 当右节点已经被访问过或者左节点不存在的情况,就去访问根节点 if (current.left == null || current.left == preview) { treeNodes.pop(); current.right = preview; current.left = null; preview = current; current = null; } else { current = current.left; } }} 补充说明:先序遍历 在介绍着后序遍历的时候,我们先用先序遍历的例子以及缺陷,来说明为什么我们选择后序遍历。那么,就一定不能用先序遍历了吗?显然,答案是不对的。 有一种特殊的先序遍历,提前将右节点保存到栈中,我们利用这种遍历方式就可以防止右节点的丢失。因为栈是先进后出,所以我们先将右节点入栈。 再根据上面先序遍历的分析,因为我们用栈保存了右孩子,所以不需要担心右孩子丢失了。用一个 pre 变量保存上次遍历的节点即可。 public static void flatten1(TreeNode root) { if (root == null){ return; } Stack<TreeNode> s = new Stack<TreeNode>(); s.push(root); TreeNode pre = null; while (!s.isEmpty()) { TreeNode temp = s.pop(); if(pre!=null){ pre.right = temp; pre.left = null; } if (temp.right != null){ s.push(temp.right); } if (temp.left != null){ s.push(temp.left); } pre = temp; }} 结语 二叉树,是一颗神奇的树,理论上我们都可以通过先序、中序、后续遍历来拆解他,得到我们想要的结果,在做题的时候也是如此。 但是真正体现到编程的世界里,还是和理论做题有一点不同,编程需要我们用机器语言是实现,去思考,去打通我们算法的任督二脉,这样就是LeetCode存在的魅力,他是一个氛围很好的社区,拥有它,就拥有了算法的世界,拥有了进阶的可能。 安利了LeetCode,安利下自己的号,尽量做到每周一题,分模块的学习。小编最大的后悔就是没能在大学学好数据结构和算法这门课,现在吃亏了,吃大亏了。好在万变不离其宗,只要通过自己的勤奋,没有什么是不可能的。 作者:Dimple |
|