二叉树展开为链表

发布于 — 2020 年 03 月 03 日
#树

题目链接

力扣

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

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

一边遍历一边修改树

维护一个指针，表示上一次的节点， 从栈中获取到节点后，如果上一次节点不为null，则将其左节点置为null，右节点置为当前访问节点 如果左右节点不为null，则将它们放入栈中，但是要注意需要先放右节点

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22

public void flatten(TreeNode root) {
		if (root == null) {
			return;
		}
		Stack<TreeNode> stack = new Stack<TreeNode>();
		stack.push(root);
		TreeNode prev = null;
		while (!stack.isEmpty()) {
			TreeNode curr = stack.pop();
			if (prev != null) {
				prev.left = null;
				prev.right = curr;
			}
			if (curr.right != null) {
				stack.push(curr.right);
			}
			if (curr.left != null) {
				stack.push(curr.left);
			}
			prev = curr;
		}
	}

先中序遍历再构建结果

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20

public void flatten(TreeNode root) {
		List<TreeNode> list = new ArrayList<TreeNode>();
		Deque<TreeNode> stack = new LinkedList<TreeNode>();
		TreeNode node = root;
		while (node != null || !stack.isEmpty()) {
			while (node != null) {
				list.add(node);
				stack.push(node);
				node = node.left;
			}
			node = stack.pop();
			node = node.right;
		}
		int size = list.size();
		for (int i = 1; i < size; i++) {
			TreeNode prev = list.get(i - 1), curr = list.get(i);
			prev.left = null;
			prev.right = curr;
		}
	}