二叉树展开为链表

> https://leetcode.cn/problems/flatten-binary-tree-to-linked-list/description/

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

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

### 思路
题解参考：https://blog.csdn.net/Enthusiastic_boy/article/details/122367693
重要的是这个点：找到当前节点左子树先序遍历的最后一个节点，然后把它挂在当前节点的右子树上，当前节点的左子树变右子树。顺序遍历当前节点直至为null即可。
![](https://minio.riun.xyz/riun1/2022-11-11_2hSzAOAnkVM97UrnxI.jpg)

### 代码：
```java
package com.example.demo.leecode;

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;

public TreeNode() {
    }
    public TreeNode(int val) {
        this.val = val;
    }
    public TreeNode(int val, TreeNode left, TreeNode right) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}

public class Solution {

public static void main(String[] args) {
        TreeNode treeNode1 = new TreeNode(1);
        TreeNode treeNode2 = new TreeNode(2);
        TreeNode treeNode3 = new TreeNode(3);
        TreeNode treeNode4 = new TreeNode(4);
        TreeNode treeNode5 = new TreeNode(5);
        TreeNode treeNode6 = new TreeNode(6);
        treeNode1.left = treeNode2;
        treeNode1.right = treeNode5;
        treeNode2.left = treeNode3;
        treeNode2.right = treeNode4;
        treeNode5.right = treeNode6;

Solution solution = new Solution();
        solution.flatten(treeNode1);
    }

public void flatten(TreeNode root) {
        if (root == null) {
            return;
        }
        TreeNode cur = root;
        while (cur != null) {
            TreeNode leftLastNode = getLeftLastNode(cur.left);
            if (leftLastNode != null) {
                leftLastNode.right = cur.right;
                cur.right = cur.left;
                cur.left = null;
            }
            cur = cur.right;
        }
    }

//传入cur的left
    public TreeNode getLeftLastNode(TreeNode node) {
        if (node == null) {
            return null;
        }
        while (node.right != null) {
            node = node.right;
        }
        return node;
    }
}

```

二叉树展开为链表

发表评论