题目描述:
给你二叉树的根节点 root ,返回它节点值的 前序 遍历。
示例1:
输入:root = [1,null,2,3]
输出:[1,2,3]
示例 2:
输入:root = []
输出:[]
public ListLeetCode 114二叉树展开为链表preorderTraversal(TreeNode root) { List ans = new ArrayList<>(); preorder(root, ans); return ans; } private void preorder(TreeNode root, List ans) { if (root == null) { return; } ans.add(root.val); preorder(root.left, ans); preorder(root.right, ans); }
题目描述:
给你二叉树的根结点 root ,请你将它展开为一个单链表:
展开后的单链表应该同样使用 TreeNode ,其中 right 子指针指向链表中下一个结点,而左子指针始终为 null 。
展开后的单链表应该与二叉树 先序遍历 顺序相同。
示例1:
输入:root = [1,2,5,3,4,null,6]
输出:[1,null,2,null,3,null,4,null,5,null,6]
示例 2:
输入:root = []
输出:[]
- 时间复杂度:O(n)。其中 n 是二叉树的节点数。展开为单链表的过程中,需要对每个节点访问一次,在寻找前驱节点的过程中,每个节点最多被额外访问一次。
- 空间复杂度:O(1)
public void flatten(TreeNode root) {
TreeNode curr = root;
while (curr != null) {
if (curr.left != null) {
TreeNode next = curr.left;
TreeNode predecessor = next;
while (predecessor.right != null) { // 找到cur左子树的前序最后一个节点
predecessor = predecessor.right;
}
predecessor.right = curr.right; // 连接cur子树前序的最后一个节点和右子树
curr.left = null; // 部分伸展
curr.right = next;
}
curr = curr.right; // cur.right也即使是原来cur的左节点,之后继续往左遍历,连接左子树最右边节点和其它部分【遍历到最后总会伸展完】
}
}



