首页 > 代码库 > LeetCode-114 Flatten Binary Tree to Linked List

LeetCode-114 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.

 

分析:

使用递归,存储原始树的左子树。需要注意的是题目要求in-place,因此不能用new TreeNode(X)构造新节点并作为结果返回。

 

代码如下:

 1 class TreeNode { 2     int val; 3     TreeNode left; 4     TreeNode right; 5     TreeNode(int x) { val = x; } 6 } 7  8 public class Solution { 9     public void flatten(TreeNode root) {10         if(root != null) {11             TreeNode left = root.left;12             TreeNode right = root.right;13             14             root.left = null;15             root.right = left;16             flatten(root.right);17             18             while(root.right != null) {19                 root = root.right;20             }21             22             root.right = right;23             flatten(root.right);24         }26     }27 }

 

LeetCode-114 Flatten Binary Tree to Linked List