首页 > 其他 > 详细

给定一个二叉树,原地将它展开为一个单链表。

时间:2020-08-02 23:56:07      阅读:125      评论:0      收藏:0      [点我收藏+]

例如,给定二叉树

    1
   /   2   5
 / \   3   4   6
将其展开为:
1
   2
       3
           4
               5
                   6
python:(官方解法:前序遍历)
# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution(object):
    def flatten(self, root):
        """
        :type root: TreeNode
        :rtype: None Do not return anything, modify root in-place instead.
        """
        preordList = list()
        def preorderTraversal(root):
            if root:
                preordList.append(root)
                preorderTraversal(root.left)
                preorderTraversal(root.right)
        preorderTraversal(root)
        size = len(preordList)
        for i in range(1,size):
            prev,curr = preordList[i-1],preordList[i]
            prev.left = None
            prev.right = curr

go:

func flatten(root *TreeNode)  {
    list := preorderTraversal(root)
    for i := 1; i < len(list); i++ {
        prev, curr := list[i-1], list[i]
        prev.Left, prev.Right = nil, curr
    }
}

func preorderTraversal(root *TreeNode) []*TreeNode {
    list := []*TreeNode{}
    if root != nil {
        list = append(list, root)
        list = append(list, preorderTraversal(root.Left)...)
        list = append(list, preorderTraversal(root.Right)...)
    }
    return list
}

 

给定一个二叉树,原地将它展开为一个单链表。

原文:https://www.cnblogs.com/ghl666/p/13423702.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!