LeetCode114--二叉树展开为链表

一、题目说明

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

a

二、分析

  • 根据题目里给出的示例可以知道我们需要把二叉树按前序遍历的顺序原地展开为链表。

  • 我们知道前序遍历的顺序为根-->左-->右,算法需要保证在改变指针指向的时候保持遍历结果不变

  • 对于右子树的根节点,可以知道它的前驱结点是左子树的最右下的结点,当我们把整个右子树接到前驱结点的右指针时,树的前序遍历保持不变。此时再把新的左子树换的根节点的左指针,一直这样迭代下去的话二叉树就变成了链表。

    a

三、解题代码

1.C++

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
void flatten(TreeNode* root) {
while(root != NULL){
if(root->left != NULL){
TreeNode* pre = root->left;
//找最右边的节点
while(pre->right != NULL)
pre = pre->right;
//将root的右子树接到后面
pre->right = root->right;
root->right = root->left;
root->left = NULL;
}
root = root->right;
}
}
};

2.Python

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution:
def flatten(self, root: TreeNode) -> None:
"""
Do not return anything, modify root in-place instead.
"""
head = root
while head != None:
#将右子树接在head的前驱节点后面
if head.left != None:
pre = head.left
#找到前驱节点
while pre.right != None:
pre = pre.right
#拼接
pre.right = head.right
head.left, head.right = None, head.left
head = head.right

3.Go

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
/**
* Definition for a binary tree node.
* type TreeNode struct {
* Val int
* Left *TreeNode
* Right *TreeNode
* }
*/
func flatten(root *TreeNode) {
head := root
for head != nil {
//将右子树接在head的前驱节点后面, 并交换左右子树
if head.Left != nil {
pre := head.Left
//找到前驱节点
for pre.Right != nil {
pre = pre.Right
}
//拼接, 并交换
pre.Right = head.Right
head.Left, head.Right = nil, head.Left
}
head = head.Right
}
}
------------- 本文结束 感谢您的阅读 -------------

本文标题:LeetCode114--二叉树展开为链表

文章作者:Perry

发布时间:2019年04月21日 - 14:57

最后更新:2019年09月19日 - 13:46

原始链接:https://perry96.com/archives/ab07ff2a.html

许可协议: 署名-非商业性使用-禁止演绎 4.0 国际 转载请保留原文链接及作者。

0%