摘要:题目解答这里有三种方法,三种方法是三种思考问题的思路,都掌握才好。的解法的解法的解法
题目:
Given a binary tree, return the preorder traversal of its nodes" values.
For example:
Given binary tree {1,#,2,3},
1
2 /
3
return [1,2,3].
解答:
这里有三种方法,三种方法是三种思考问题的思路,都掌握才好。
1.Iterative的解法:
public ListpreorderTraversal(TreeNode root) { List result = new ArrayList (); Stack stack = new Stack (); if (root == null) return result; stack.push(root); while (!stack.isEmpty()) { TreeNode node = stack.pop(); if (node.right != null) { stack.push(node.right); } if (node.left != null) { stack.push(node.left); } result.add(node.val); } return result; }
2.Recursive的解法:
public void Traverse(TreeNode root, Listresult) { if (root == null) return; result.add(root.val); Traverse(root.left, result); Traverse(root.right, result); } public List preorderTraversal(TreeNode root) { List result = new ArrayList (); Traverse(root, result); return result; }
3.Divide & Conquer的解法
public ListpreorderTraversal(TreeNode root) { List result = new ArrayList (); if (root == null) return result; List left = preorderTraversal(root.left); List right = preorderTraversal(root.right); result.add(root.val); result.addAll(left); result.addAll(right); return result; }
文章版权归作者所有,未经允许请勿转载,若此文章存在违规行为,您可以联系管理员删除。
转载请注明本文地址:https://www.ucloud.cn/yun/64890.html
589. N-ary Tree Preorder Traversal Given an n-ary tree, return the preorder traversal of its nodes values.For example, given a 3-ary tree:showImg(https://segmentfault.com/img/bVbhKkv?w=781&h=502);Retu...
摘要:指的是的位置。算法比较简单,算法比较难想,可是原题都说了 preorder: root-left-rightinorder: left-root-rightpostorder: left-right-root order指的是root的位置。 recursive算法比较简单,iterative算法比较难想,可是leetcode原题都说了: recursive method is tri...
摘要:二分法复杂度时间空间思路我们先考察先序遍历序列和中序遍历序列的特点。对于中序遍历序列,根在中间部分,从根的地方分割,前半部分是根的左子树,后半部分是根的右子树。 Construct Binary Tree from Preorder and Inorder Traversal Given preorder and inorder traversal of a tree, constru...
摘要:当你被的时候,人家问,一定要说,当然可以啦所以,不用,怎么办幸好,这是一道的题目,只要逐层遍历,就可以了。所以,试一试用堆栈的做法吧记得的特点是后入先出哦 Problem Given a binary tree, return the preorder traversal of its nodes values. Example Given: 1 / 2 3 ...
摘要:思路在的顺序里,先,然后再左右。所以根据可以知道的。接着再分别在和的里面重复找以及左右的过程。首先的包括和,以及对应的起始和结束位置,对应的起始和结束位置。返回值为,因为每个里要一个,同时找到它的和,左右节点通过返回值获得。同时的不需要了。 From Preorder and Inorder 思路在preorder的顺序里,先root,然后再左右。所以根据preorder可以知道roo...
阅读 1506·2021-11-04 16:10
阅读 2686·2021-09-30 09:48
阅读 2810·2019-08-29 11:31
阅读 1513·2019-08-28 18:22
阅读 3186·2019-08-26 13:44
阅读 1295·2019-08-26 13:42
阅读 2823·2019-08-26 10:20
阅读 692·2019-08-23 17:00