【重点】【二叉树】114. 二叉树展开为链表
题目
法1：先序遍历
思路不够好
// 递归版遍历
class Solution {public void flatten(TreeNode root) {List<TreeNode> nodeList = new ArrayList<>();preorder(root, nodeList);for (int i = 0; i < nodeList.size(); ++i) {TreeNode curNode = nodeList.get(i);curNode.left = null;if (i == nodeList.size() - 1) {curNode.right = null;} else {curNode.right = nodeList.get(i + 1);}}}public void preorder(TreeNode root, List<TreeNode> res) {if (root == null) {return;}res.add(root);preorder(root.left, res);preorder(root.right, res);}
}// 迭代版遍历
class Solution {public void flatten(TreeNode root) {List<TreeNode> nodeList = new ArrayList<>();Stack<TreeNode> stack = new Stack<>();while (root != null || !stack.isEmpty()) {if (root != null) {nodeList.add(root);stack.push(root);root = root.left;} else {TreeNode tmp = stack.pop();root = tmp.right;}}for (int i = 0; i < nodeList.size(); ++i) {TreeNode curNode = nodeList.get(i);curNode.left = null;if (i == nodeList.size() - 1) {curNode.right = null;} else {curNode.right = nodeList.get(i + 1);}}}
}
法2：规律+迭代解法
参考答案很多：https://leetcode.cn/problems/flatten-binary-tree-to-linked-list/solutions/17274/xiang-xi-tong-su-de-si-lu-fen-xi-duo-jie-fa-by–26/?envType=study-plan-v2&envId=top-100-liked
重点记住下面这个！！！
class Solution {public void flatten(TreeNode root) {TreeNode cur = root;while (cur != null) {if (cur.left == null) {cur = cur.right;} else {TreeNode pre = cur.left; // 记录左子树的最右边节点while (pre.right != null) {pre = pre.right;}pre.right = cur.right;cur.right = cur.left;cur.left = null;cur = cur.right;}}}
}