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.

原题链接：https://oj.leetcode.com/problems/flatten-binary-tree-to-linked-list/

题目：给定二叉树，按前序位置展平成一个链表。

思路：递归处理。把右子树放到左子树之后，并清空左子树。

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

相同的做法。可是非递归。

public void flatten(TreeNode root){		while(root != null){			if(root.left != null){				TreeNode tmp = root.left;				while(tmp.right != null)					tmp = tmp.right;				tmp.right = root.right;				root.right = root.left;				root.left = null;			}			root = root.right;		}	}

reference : http://blog.csdn.net/perfect8886/article/details/20000083

版权声明：本文博客原创文章，博客，未经同意，不得转载。