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
题意说明:将一个二叉树依照前序遍历变为一个链表。
解题思路:思路很简单,对二叉树进行前序遍历,把每次找到的节点加到链表的末节点。
Java不同于C++可以使用引用保证调用函数的同时可以不断更新链表末节点为当前节点,所以使用一个只有一个元素的数组来模拟引用。
AC代码:
/** * Definition for binary tree * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */ public class Solution { public void flatten_re(TreeNode root, TreeNode[] current) { if(root==null) { return; } TreeNode left = root.left; TreeNode right = root.right; if(left!=null) { root.left = null; } current[0].right = root; current[0] = root; if(left!=null) { flatten_re(left,current); } if(root.right!=null) { flatten_re(right,current); } return; } public void flatten(TreeNode root) { if(root==null) { return; } if(root.left==null&&root.right==null) { return; } TreeNode [] array = new TreeNode[1]; array[0] = root; flatten_re(root,array); return; } }