首页 > 代码库 > LeetCode 114. Flatten Binary Tree to Linked List
LeetCode 114. Flatten Binary Tree to Linked List
原题
Given a binary tree, flatten it to a linked list in-place.
For example,
Given1 / 2 5 / \ 3 4 6
The flattened tree should look like:
1 2 3 4 5 6Hints:If you notice carefully in the flattened tree, each node‘s right child points to the next node of a pre-order traversal.
题目大意就是让你将一个二叉树转化为一个只有右子节点的扁平树，且每一个节点的右孩子都是他前序遍历的下一个节点
解题思路
思路一：按照该树的前序遍历结果，重新构造扁平树
思路二：循环遍历，每次将节点的右子树接到左子树的最右节点下，然后再将左子树赋值给右子树，左子树置为空，直到循环到最底层节点为止
思路三：正向递归，既然每一个节点的右孩子都是他前序遍历的下一个节点，那么可以采取反向后序遍历的方式，这样遍历的结果和前序遍历的值正好是互逆的。
代码实现
思路一：
# Definition for a binary tree node.# class TreeNode(object):# def __init__(self, x):# self.val = x# self.left = None# self.right = None# 先序遍历，然后将遍历结果重新赋值给rootclass Solution(object): def flatten(self, root): """ :type root: TreeNode :rtype: void Do not return anything, modify root in-place instead. """ self.POrder = [] self.preOrder(root) if len(self.POrder) == 0: return del self.POrder[0] root.left = None for i in self.POrder: root.right = TreeNode(i) root = root.right def preOrder(self, node): if node == None: return self.POrder.append(node.val) self.preOrder(node.left) self.preOrder(node.right)
思路二：
# Definition for a binary tree node.# class TreeNode(object):# def __init__(self, x):# self.val = x# self.left = None# self.right = None# 循环，每次将右子树接到左子树的最右节点下，然后再将左子树赋值给右子树，左子树置为空class Solution(object): def flatten(self, root): """ :type root: TreeNode :rtype: void Do not return anything, modify root in-place instead. """ while root: if root.left: itr = root.left while itr.right: itr = itr.right itr.right = root.right root.left, root.right = None, root.left root = root.right
思路三：
/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */public class Solution { private TreeNode prev = null; public void flatten(TreeNode root) { if (root == null) return; flatten(root.right); flatten(root.left); root.right = prev; root.left = null; prev = root;}}
LeetCode 114. Flatten Binary Tree to Linked List
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。