二叉树展开链表

https://leetcode.cn/problems/flatten-binary-tree-to-linked-list/description/?envTypestudy-plan-v2envIdtop-100-liked题目思路先序遍历跟 - 左 - 右 。最后我们要拼接成的序列为 1 - 2 - 3 - 4 - 5 - 6如果正着做从 1 开始当把结点 1 的right 指向 结点 2 时结点 1 的右子树就会丢失。为了防止它丢失需要额外设置和维护变量指向 右子树 很麻烦如果反着做从 6 开始从链表的尾部开始拼接 把结点 6 拼接到结点 5 的后面把 结点5 插入到结点 4 的后面 ……以此类推 。 当处理 结点 1 时它的左子树 和 右子树已经形成了一条排好序的链条只需要 1.left null; 1.right head; head 1;倒着遍历 右 - 左 - 跟 遍历的结果正好是前序遍历的逆序生成一个结点head它指向已经排好序的链条的头节点当我们给每个结点设置 node.left null; 和 node.right head时它的左右结点已经遍历过了可以放心设置。node.right 设置为head是为了维护二叉树遍历的顺序 满足倒着遍历 右 - 左 - 跟。node.left设置为null是为了去除当前node的原有干扰分支代码class Solution { private TreeNode head null; public void flatten(TreeNode root) { if(root null) return; flatten(root.right); flatten(root.left); root.left null; root.right head; head root; } }