二叉树展开为链表

LeetCode 114 : 二叉树展开为链表
描述:
给你二叉树的根结点 root ，请你将它展开为一个单链表：

• 展开后的单链表应该同样使用 TreeNode ，其中 right 子指针指向链表中下一个结点，而左子指针始终为 null 。
• 展开后的单链表应该与二叉树 先序遍历 顺序相同。

解法一 : 递归解法

解题思路:

1. 使用前序遍历的方法,添加到list当中
2. 遍历list中的元素,让i下标节点的左子树为空,右子树指向i+1下标的节点.

代码实现:

class Solution {
    public void flatten(TreeNode root) {
        List<TreeNode> list = new ArrayList<TreeNode>();
        preorderTraversal(root, list);
        for (int i = 0; i < list.size() - 1; i++) {
            list.get(i).left = null;
            list.get(i).right = list.get(i+1);
        }
    }
    public void preorderTraversal(TreeNode root, List<TreeNode> list) {
        if (root == null) return;
        list.add(root);
        preorderTraversal(root.left, list);
        preorderTraversal(root.right, list);
    }
}

解法二 : 迭代解法

解题思路:

1. 使用栈的后进先出的特性,记录下前一个节点.
2. 如果栈不为空,或者该节点不为空,进入循环,如果该节点不为空,入栈,并插入到list当中.循环该节点的左子树,直到为空停止循环.
3. 如果左子树为空,则出栈顶元素,再循环遍历栈顶节点的右子树.
4. 如果栈为空,并且节点也遍历完了,就结束循环.
5. 然后再遍历list 和 方法一的步骤一致.

代码实现:

class Solution {
    public void flatten(TreeNode root) {
        if(root == null) return;
        Stack<TreeNode> stack = new Stack<>();
        List<TreeNode> list = new ArrayList<>();
        TreeNode cur = root;
        //cur 不为空 或 栈 不为空 进入循环
        while(cur != null || !stack.isEmpty()){
            while(cur != null){
                stack.push(cur);//cur不为空就入栈
                list.add(cur);//入栈的同时插入到list中
                cur = cur.left;//根->左的顺序
            }
            TreeNode top = stack.pop();
            cur = top.right;//根->左 结束之后 就开始 右
        }
        //遍历list
        for (int i = 0; i < list.size() - 1; i++) {
            list.get(i).left = null;
            list.get(i).right = list.get(i+1);
        }
    }
}

解法三 : 前驱节点 空间复杂度O(1)

解题思路:

1. 始终让根节点的右子树连接到左子树的右子树,让根的左子树变成根的右子树,左子树置空,然后让root = root.right.
2. 如果根节点不为空,引用cur指向root.
3. 如果root的左子树不为空,引用一个curNext指向root.left;
4. 引用一个pre指向curNext,循环直到pre.right = null,如果pre.right != null,让pre = pre.right. 如果循环结束,pre.right == null. 让pre.right = cur. right.
5. 让cur.left = null, cur.right = curNext; cur = cur.right;
6. 循环 2~4 步骤.

画图解析:

代码实现:

class Solution {
    public void flatten(TreeNode root) {
        if(root == null) return;
        TreeNode cur = root;
        TreeNode curNext = null;
        while (cur != null){
            if(cur.left != null){
                curNext = cur.left;
            	TreeNode pre = curNext;
            	//让pre指向左子树的最右节点
           		while (pre.right != null){
                	pre = pre.right;
            	}
            	//让左子树最右节点和右子树链接
	           	pre.right = cur.right;
            	//让根节点的左边断开
            	cur.left = null;
            	//让根节点的右子树连接左子树
            	cur.right = curNext;
            }
            cur = cur.right;
        }
    }
}