首页 > 代码库 > 【leetcode刷题笔记】Flatten Binary Tree to Linked List
【leetcode刷题笔记】Flatten Binary Tree to Linked List
Given a binary tree, flatten it to a linked list in-place.
For example,
Given
1 / 2 5 / \ 3 4 6
The flattened tree should look like:
1 2 3 4 5 6
Hints:
If you notice carefully in the flattened tree, each node‘s right child points to the next node of a pre-order traversal.
题解：可以看出flatten以后得到的树其实就是原来树的先序遍历，并且所得到的树的左子都有null，右子都是原树先序遍历时的下一个节点。
利用递归先序遍历树即可，用lastNode保存上一个节点的信息，并且在递归过程中要注意保存根节点的右子，因为在递归遍历左子树的过程中，会把根节点的右子指针重新赋值，右子树会丢失。
代码如下：
1 /** 2 * Definition for binary tree 3 * public class TreeNode { 4 * int val; 5 * TreeNode left; 6 * TreeNode right; 7 * TreeNode(int x) { val = x; } 8 * } 9 */10 public class Solution {11 private TreeNode lastNode = null;12 public void flatten(TreeNode root) {13 if(root == null)14 return;15 16 if(lastNode != null){17 lastNode.left = null;18 lastNode.right = root;19 }20 21 lastNode = root;22 23 TreeNode right = root.right;24 flatten(root.left);25 flatten(right);26 }27 }
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。