阿里云clouder网站建设,中太建设集团网站,网络推广营销培训机构,寒亭区住房和城乡建设局网站目录
题目描述#xff1a;
解法一#xff1a;递归法
解法二#xff1a;迭代法
解法三#xff1a;Morris 遍历 二叉树的前序遍历
题目描述#xff1a;
给你二叉树的根节点 root #xff0c;返回它节点值的 前序 遍历。
示例 1#xff1a; 输入#xff1a;root […目录
题目描述
解法一递归法
解法二迭代法
解法三Morris 遍历 二叉树的前序遍历
题目描述
给你二叉树的根节点 root 返回它节点值的 前序 遍历。
示例 1 输入root [1,null,2,3]
输出[1,2,3]
示例 2
输入root []
输出[]示例 3
输入root [1]
输出[1]
示例 4 输入root [1,2]
输出[1,2]
示例 5 输入root [1,null,2]
输出[1,2]提示
树中节点数目在范围 [0, 100] 内-100 Node.val 100
解法一递归法 ListInteger res new ArrayList();public ListInteger preorderTraversal(TreeNode root) {if(root null){return res;}res.add(root.val);preorderTraversal(root.left);preorderTraversal(root.right);return res;}
复杂度分析
时间复杂度O(n)O(n)其中 nn 是二叉树的节点数。每一个节点恰好被遍历一次。空间复杂度O(n)O(n)为递归过程中栈的开销平均情况下为 O(\log n)O(logn)最坏情况下树呈现链状为 O(n)O(n)。
解法二迭代法 public ListInteger preorderTraversal(TreeNode root) {ListInteger res new ArrayList();if(root null){return res;}DequeTreeNode stack new ArrayDeque();stack.push(root);while(!stack.isEmpty()){TreeNode temp stack.pop();res.add(temp.val);if(temp.right ! null){stack.push(temp.right);}if(temp.left ! null){stack.push(temp.left);}}return res;}
复杂度分析
时间复杂度O(n)O(n)其中 nn 是二叉树的节点数。每一个节点恰好被遍历一次。空间复杂度O(n)O(n)为迭代过程中显式栈的开销平均情况下为 O(\log n)O(logn)最坏情况下树呈现链状为 O(n)O(n)。
解法三Morris 遍历 public ListInteger preorderTraversal(TreeNode root) {ListInteger res new ArrayListInteger();if (root null) {return res;}TreeNode p1 root, p2 null;while (p1 ! null) {p2 p1.left;if (p2 ! null) {while (p2.right ! null p2.right ! p1) {p2 p2.right;}if (p2.right null) {res.add(p1.val);p2.right p1;p1 p1.left;continue;} else {p2.right null;}} else {res.add(p1.val);}p1 p1.right;}return res;}复杂度分析
时间复杂度O(n)O(n)其中 nn 是二叉树的节点数。没有左子树的节点只被访问一次有左子树的节点被访问两次。空间复杂度O(1)O(1)。只操作已经存在的指针树的空闲指针因此只需要常数的额外空间。
