首页 > 代码库 > [LeetCode] 114. Flatten Binary Tree to Linked List Java

[LeetCode] 114. Flatten Binary Tree to Linked List Java

题目:

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

题意及分析:给出一棵树,要求给出这棵树的先序遍历组成的链表,但是还是用树表示。首先找到根节点左子节点的最右子节点,然后将根节点的右子树移到该点的右节点上;再将根节点的左子节点移到根节点的右子节点上,并将根节点左子树重置为null;然后将根节点向右子节点移动一位,递归即可。

代码:

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
   public void flatten(TreeNode root) {
        if(root==null) return;
        if(root.left!=null){
            TreeNode cur = root.left;
            while(cur.right!=null){
                cur=cur.right;
            }
            cur.right=root.right;
            root.right=root.left;
            root.left=null;
        }
        flatten(root.right);
    }
}

 

 

 

[LeetCode] 114. Flatten Binary Tree to Linked List Java