中国城乡建设协会网站,wordpress怎样下载文件,长宁区网站建设设计,全网推广营销题目#xff1a;
给你二叉树的根结点 root #xff0c;请你将它展开为一个单链表#xff1a;
展开后的单链表应该同样使用 TreeNode #xff0c;其中 right 子指针指向链表中下一个结点#xff0c;而左子指针始终为 null 。展开后的单链表应该与二叉树 先序遍历 顺序相同…题目
给你二叉树的根结点 root 请你将它展开为一个单链表
展开后的单链表应该同样使用 TreeNode 其中 right 子指针指向链表中下一个结点而左子指针始终为 null 。展开后的单链表应该与二叉树 先序遍历 顺序相同。
方法一先前序遍历然后再修改左右指针
class Solution {public void flatten(TreeNode root) {ListTreeNode list new ArrayListTreeNode();preorderTraversal(root, list);int size list.size();for(int i 1; i size; i) {TreeNode pre list.get(i - 1), cur list.get(i);pre.right cur;pre.left null;}}private void preorderTraversal(TreeNode root, ListTreeNode list) {if (root null)return;list.add(root);preorderTraversal(root.left, list);preorderTraversal(root.right, list);}
} 方法二寻找前驱节点 class Solution {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) {predecessor predecessor.right;}predecessor.right curr.right;curr.left null;curr.right next;}curr curr.right;}}
}
