Given a binary tree, flatten it to a linked list in-place.
For example, given the following tree:
1 / 2 5 / \ 3 4 6
The flattened tree should look like:
1
2
3
4
5
6
每个节点的右节点都是preorder traverse的下一个节点 -> 应该先 反preorder遍历 (即node.right->node.left->node) 到最后，从最后开始relink
time: O(n), space: O(height)
/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */ class Solution { TreeNode prev = null; public void flatten(TreeNode root) { if(root == null) { return; } flatten(root.right); flatten(root.left); root.right = prev; root.left = null; prev = root; } }
114. Flatten Binary Tree to Linked List - Medium
原文：https://www.cnblogs.com/fatttcat/p/10202108.html