法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：规律+迭代解法
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;
}
}
}
}
