题目来源
https://leetcode.com/problems/flatten-binary-tree-to-linked-list/
Given a binary tree, flatten it to a linked list in-place.
题意分析
Input: binary tree
Output: flattened tree
Conditions:将一个二叉树压平为一个flatten 树,也就是一条斜线
题目思路
先将左右子树压平,然后将左子树嵌入到本节点与右子树之间。
AC代码(Python)
# 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.
"""
if root == None:
return
self.flatten(root.left)
self.flatten(root.right)
p = root
if p.left == None:
return
p = p.left
while p.right:
p = p.right
p.right = root.right
root.right = root.left
root.left = None