[leetcode]114. Flatten Binary Tree to Linked List将二叉树展成一个链表

Given a binary tree, flatten it to a linked list in-place.

For example, given the following tree:

1 / \ 2 5 / \ \ 3 4 6

The flattened tree should look like:

1 \ 2 \ 3 \ 4 \ 5 \ 6

题目

将左子树所形成的链表插入到root和root->right之间

 

思路

1 / 2(root) 假设当前root为2 / \ 3(p) 4 1 / 2(root) / \ 3(p)—— 4(root.right) p.right = root.right 1 / 2(root) / \ 3(root.right)- 4 root.right = root.left 1 / 2(root) \ 3(root.right)- 4 root.left - null

代码

1 class Solution { 2 public void flatten(TreeNode root) { 3 if (root == null) return; // 终止条件 4 // recursion 5 flatten(root.left); 6 flatten(root.right); 7 8 if (root.left == null) return; 9 10 // 三方合并，将左子树所形成的链表插入到root和root->right之间 11 TreeNode p = root.left; 12 while(p.right != null) { 13 p = p.right; //寻找左链表最后一个节点 14 } 15 p.right = root.right; 16 root.right = root.left; 17 root.left = null; 18 } 19 }

 

转载于:https://www.cnblogs.com/liuliu5151/p/9823988.html

相关资源：数据结构—成绩单生成器