问题描述:
Given a binary tree, flatten it to a linked list in-place.
For example,
Given
1 / \ 2 5 / \ \ 3 4 6
The flattened tree should look like:
1 \ 2 \ 3 \ 4 \ 5 \ 6
If you notice carefully in the flattened tree, each node's right child points to the next node of a pre-order traversal.
原问题链接:https://leetcode.com/problems/flatten-binary-tree-to-linked-list/
问题分析
第一种思路
这个问题很容易想到第一种思路。按照前面提示所说到,在前面要求的转换方式里,正好是一个对树进行前序遍历形成的序列。而且这里要求最后形成的队列结构是对应到每个节点的右子节点连接下一个节点。所以我们可以先考虑前序遍历的方式。
在前序遍历里,我们每次访问当前的元素之后,就要去访问它的左子节点,然后再去访问它的右子节点。这是一种递归访问的方式。在这里因为要修改节点,使得它成为一个链表,用原生的树前序递归访问的方式不太方便。于是我们可以考虑用非递归的方式来访问它们。同时,在每次访问的时候我们将顺序访问的节点给调整拼接成一个链表。具体来说,针对两个方面。
首先,该怎么去遍历它们呢?我们可以采用一个栈,每次访问某个节点的时候,将这个节点的右子节点压入栈中。当然,这是在节点的右子节点存在的情况下。处理完这个节点之后然后继续访问该节点的左子节点。另外,该怎么来根据顺序修改它们的链接呢?一种方式是采用一个队列,每次访问到的元素将它们加入队列。然后再每次从队列里取元素,进行调整。按照这种思路可以实现如下的代码:
/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */ public class Solution { public void flatten(TreeNode root) { if(root == null) return; TreeNode node = root; Deque<TreeNode> stack = new LinkedList<>(); Queue<TreeNode> queue = new LinkedList<>(); while(node != null || !stack.isEmpty()) { if(node != null) { queue.add(node); if(node.right != null) stack.push(node.right); node = node.left; } else if(!stack.isEmpty()) { node = stack.pop(); } } node = queue.remove(); node.left = null; while(!queue.isEmpty()) { TreeNode temp = queue.remove(); node.right = temp; temp.left = node; node = temp; } } }
实际上,在执行这部分代码的时候,会导致内存的使用超过问题的要求了。因为原问题里要求是in place的方式。所以不能占据太多的内存空间。那么就算是我们采用一个辅助的栈,其对空间的占用也还是会有一定影响的。因此这种方式可以作为实际中的一个解决思路。但是对这个问题并不适用。
第二种方法
既然前面的那种思路不可行,我们看看还有没有其他的思路。我们看前面调整的过程,对于根节点来说,它的下一个节点在左子节点存在的情况下,就是它的左子节点。所以在变换中会将它的右指针指向它的左子节点。在原来的过程中,将左子节点遍历完之后才会去遍历它的右子节点。所以在左子树中最后遍历的那个节点是它左子节点最右下角的那个节点。
这样,我们可以概括出这样的一个过程。每次根据一个节点,找它左子节点的最右下角的元素。如果有,将这个元素的right指向根节点的右子节点。然后根节点的right指向它的左子节点。再指向它的下一个位置。也就是它的right节点。
详细的实现如下:
/** * Definition for binary tree * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */ public class Solution { public void flatten(TreeNode root) { while(root != null) { if(root.left != null) { TreeNode ptr = root.left; while(ptr.right != null) ptr = ptr.right; ptr.right = root.right; root.right = root.left; root.left = null; } root = root.right; } } }
总结
这个问题的实现思路其实不止一种。有通过DFS的方式递归实现的,有通过模拟前序遍历实现的,也有通过发现它的这个规律实现的。重点在于发现具体问题的规律,结合一些数据结构来分析处理。
相关推荐
leetcode的题目:Balanced Binary Tree
leetcode做过的LeetCode的题目记录一下。对一些比较经典的题型进行分类总结。数据结构 数组 字符串 队列 链表 双指针 栈 堆 树 二叉搜索树 字典树 线段树 并查集 哈希表 图基础... Flatten Binary Tree to Linked List
leetcode卡 LeetCode 记录一下再LeetCode上刷的题,坚持每天刷一道吧 2017.06.12 打卡[LeetCode 2. Add Two Numbers], Linked list 2017.06.13 打卡[LeetCode 200. Number of Islands], BFS 2017.06.14 打卡...
BinaryTree.py是一个方便的工具,它可以构建和显示编码时所需的二叉树 演示 您需要在使用之前导入该类 import BinaryTree as bt 从值/对象列表或二叉树构造二叉树 t1 = bt.BinaryTree([1,2,3,4,5,'#',6,7,'#','#','#...
leetcode 非官方顺序leetcode题解,主要代码为Python和C++。 leetcode 第1题: leetcode 第2题: leetcode 第3题: leetcode 第4题: leetcode 第5题: leetcode 第6题: leetcode 第7题: leetcode 第9题: ...
leetcode11 top 1. 位运算 LeetCode191 : 二进制位1的个数 LeetCode338 : 比特位运算 2. 字典树 LeetCode209 : 实现一个Trie结构 LeetCode79 : 单词搜索(判断单词是否出现在给定的网格中) LeetCode212 : 单词搜索II...
LeetCode::laptop:LeetCode解决方案
leetcode 答案 leetCode :keyboard:我的 Leetcode 解题答案
lru缓存leetcode 力码 涵盖了 Geeks for Geeks 和 Leet Code 的各种问题。 LeetCode 1 : 二和 (46_Easy) LeetCode 2 : 两个数字相加 (96_Medium) LeetCode 3 : 无重复字符的最长子串 (214_Medium) LeetCode 4 : 两个...
leetcode 答案 Algorithm-In-Leetcode To solve algorithm problems in leetcode.com using Python, Golang and SQL It's my leetcode account: 这是我的LeetCode中文账户: 不仅仅是Algorithm,还有Database的题目也...
to Integer 11 Container with Most Water 14 Longest Common Prefix 15 Three Sum 16 Three Sum Closest 20 Valid Parentheses 26 Remove Duplicates from Sorted Array 48 Rotate Image 53 Maximum Subarray 55 ...
leetcode题目:Best Time to Buy and Sell Stock II
LeetCode 在LeetCode和其他编码平台上解决的问题的集合
Leetcode:Leetcode提交
:fire: Leetcode :fire: 实践使完美 :party_popper: 开玩笑的单元测试 :sparkles: 简单的代码 :artist_palette: 可读代码 入门指南 git clone https: //github.com/tangweikun/leetcode.git cd leetcode npm ...
leetcode 分类 LeetCode :bouquet::bouquet::bouquet: 介绍 leetcode 题解,Issues 会记录 leetcode 解题之路,并使用 label 进行了分类。 目录 链表
LeetCode 101:和你一起你轻松刷题(C++)
leetcode LeetCode刷题 题号是LeetCode原题,题目是自己的解答 Easy 题号 题目 Tags Star Company HashMap :star: :star: :star: Integer :star: :star: String :star: String、Stack :star: :star: :star: ...
leetcode 答案leetcode 的工具 这个项目提供了一些工具来更容易地测试 leetcode 答案。 树:切片 <-> TreeNode 此工具有助于将切片转换为 TreeNode,反之亦然。 Slice2TreeNode: []interface{} -> *model....
leetcode:leetcode刷题