LeetCode 589 N-ary Tree Preorder Traversal
給定一顆N 叉樹
的根節點,返回前序遍歷後的陣列.
例 :
給予樹: 1 / | \ 324 / \ 56 將其前序遍歷返回: [1,3,5,6,2,4].
解法
和二叉樹的前序遍歷差不多,需要注意處理好子節點的順序即可。
非遞迴解法:
/* // Definition for a Node. class Node { public int val; public List<Node> children; public Node() {} public Node(int _val,List<Node> _children) { val = _val; children = _children; } }; */ class Solution { public List<Integer> preorder(Node root) { List<Integer> list = new ArrayList<>(); if (root == null) { return list; } Stack<Node> stack = new Stack<>(); stack.add(root); while (!stack.isEmpty()) { root = stack.pop(); list.add(root.val); for (int i = root.children.size() - 1; i >= 0; i--) { stack.add(root.children.get(i)); } } return list; } }
遞迴解法:
/* // Definition for a Node. class Node { public int val; public List<Node> children; public Node() {} public Node(int _val,List<Node> _children) { val = _val; children = _children; } }; */ class Solution { List<Integer> list = new ArrayList<>(); public List<Integer> preorder(Node root) { if (root == null) { return list; } list.add(root.val); for (Node child : root.children) { preorder(child); } return list; } }
Runtime: 1 ms, faster than 100.00% of Java online submissions for N-ary Tree Preorder Traversal. Memory Usage: 47.9 MB, less than 51.19% of Java online submissions for N-ary Tree Preorder Traversal.