2020年8月2日 二叉树展开为链表 flatten
/*** Definition for a binary tree node.* public class TreeNode {* int val;* TreeNode left;* TreeNode right;* TreeNode() {}* TreeNode(int val) { this.val = val; }* TreeNode(int val, TreeNode left, TreeNode right) {* this.val = val;* this.left = left;* this.right = right;* }* }*/
class Solution {public void flatten(TreeNode root) {}
}
解题思路：
首先解释一下，题目中所提到的原地展开是什么意思。
原地算法的特点就在于，他是空间复杂度为0。不使用其他的空间，只是内部的指针互相转换来实现的算法。
比如冒泡算法就是一种经典的原地算法，在自己数组上操作，不使用额外的空间。
再看题中的排序方式，应该不难发现这是属于中序遍历二叉树生成链表。
首先缩小问题，如果是这样的二叉树，如何中序遍历？
首先，根节点肯定是不能动，由于是以右节点为单链表的连接点，所以，2应该在根节点的右边，3应该在根节点的左边。
所以，我们的操作是，左右节点互换，并且把原本的右节点连接在原本左节点末尾的右边。
知道如何解决小问题之后，我们就能尝试找出遍历的方式。
我们编写一个函数，使得我们输入一个节点，它会将其进行中序遍历重排并且返回末尾的节点。
有了这个函数之后，我们就能实现该效果。
还有不理解可以看下面的注释。
代码：
public void flatten(TreeNode root) {if(root==null)return;getEnd(root);}public TreeNode getEnd(TreeNode root){//如果左右子节点都为空，返回该节点if (root.right==root.left&&root.right==null)return root;//如果右节点为空，左节点不为空，把左节点移到右节点上开始递归else if (root.right==null&&root.left!=null){root.right=root.left;root.left=null;return getEnd(root.right);}//左节点为空，右节点不为空，直接递归右子节点if (root.left==null&&root.right!=null){return getEnd(root.right);}//如果左右节点不为空else {//先要左右互换位置，记录下右节点，将子节点移动到右节点的位置TreeNode left=root.right;root.right=root.left;root.left=null;//先对右节点递归得到右节点排序后的末尾节点TreeNode end=getEnd(root.right);//左节点移至末尾，然后递归左节点end.right=left;TreeNode end2=getEnd(end.right);return end2;}}