LeetCode 二叉树展开为链表/BiNode-一一网

这是我参与更文挑战的第 28 天，活动详情查看：更文挑战

二叉树展开为链表（114）

题目描述

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

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

示例 1：

输入：root = [1,2,5,3,4,null,6]
输出：[1,null,2,null,3,null,4,null,5,null,6]
复制代码

示例 2：

输入：root = []
输出：[]
复制代码

示例 3：

输入：root = [0]
输出：[0]
复制代码

提示：

树中结点数在范围 [0, 2000] 内
-100 <= Node.val <= 100

进阶：你可以使用原地算法（O(1) 额外空间）展开这棵树吗？

思路分析

题目要求用先序遍历的方式，其中 right 子指针指向链表中下一个结点，而左子指针始终为 null 。我们可以使用两个辅助节点进行辅助，因为题目建议我们使用原地算法进行求解，所以我们直接在节点上进行转换；我们可以在现需遍历的过程中不断给尾结点添加节点，先序遍历结束后，我们就可以拿到我们想要的节点。

代码展示

解法一：

private TreeNode dummyHead = new TreeNode();
    private TreeNode tail = dummyHead;
    public void flatten(TreeNode root) {
        preorder(root);
    }

    private void preorder(TreeNode root){
        if(root == null){
            return;
        }
        TreeNode left = root.left;
        TreeNode right = root.right;

        tail.right = root;
        tail = root;
        //需要将所有的root.left 置空
        root.left = null;

        preorder(left);
        preorder(right);


    }
复制代码

BiNode（面试题 17.12）

题目描述

二叉树数据结构TreeNode可用来表示单向链表（其中left置空，right为下一个链表节点）。实现一个方法，把二叉搜索树转换为单向链表，要求依然符合二叉搜索树的性质，转换操作应是原址的，也就是在原始的二叉搜索树上直接修改。

返回转换后的单向链表的头节点。

注意：本题相对原题稍作改动

示例 1：

输入： [4,2,5,1,3,null,6,0]
输出： [0,null,1,null,2,null,3,null,4,null,5,null,6]
复制代码

提示：

节点数量不会超过 100000。

思路分析

转换为单链表，要求依然符合二叉搜索树的性质，在原树上直接进行修改，可以看出输出是从小到大，也就是我们可以用中序遍历的方法遍历二叉搜索树，我们可以用 right 指针指向链表中下一个结点，而左子指针始终为 null 。我们可以使用两个辅助节点进行辅助，因为题目建议我们使用原地算法进行求解，所以我们直接在节点上进行转换；我们可以在现需遍历的过程中不断给尾结点添加节点，中序遍历结束后，我们就可以拿到我们想要的节点。

代码展示

解法一：

public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {

        if(root == null){
            return null;
        }
        //p或q自己是公共祖先
        if(root == p || root == q){
            return root;
        }
        //递归查找，先记录下left和right节点
        TreeNode left = lowestCommonAncestor(root.left,p,q);
        TreeNode right = lowestCommonAncestor(root.right,p,q);

        //如果left和right都找到了
        if(left != null && right != null){
            return root;
        } else if (null != left){
            return left;
        } else if (null != right){
            return right;
        }
        return null;
    }
复制代码