Leetcode N叉树遍历方式总结

灰太狼 2021-10-12 22:24 211阅读 0赞

### 文章目录 ###

*  1. 数据结构
 *  2. 前序遍历
 *  3. 后序遍历
 *  4. 层序遍历

# 1. 数据结构 #

class Node { 
        public int val;
        public List<Node> children;
    
        public Node() { 
        }
    
        public Node(int _val, List<Node> _children) { 
            val = _val;
            children = _children;
        }
    }

# 2. 前序遍历 #

[Leetcode 589. N叉树的前序遍历][Leetcode 589. N]

**递归实现**：

class Solution { 
        public List<Integer> preorder(Node root) { 
            List<Integer> res = new ArrayList<>();
            helper(root, res);
            return res;
        }
    
        private void helper(Node root, List<Integer> res) { 
            if (root == null) { 
                return;
            }
    
            res.add(root.val);
            for (Node node : root.children) { 
                helper(node, res);
            }
        }
    }

**迭代实现**：

class Solution { 
        public List<Integer> preorder(Node root) { 
            if (root == null) { 
                return new ArrayList<>();
            }
    
            List<Integer> res = new ArrayList<>();
            Stack<Node> stk = new Stack<>();
            stk.push(root);
            while (!stk.isEmpty()) { 
                Node node = stk.pop();
                res.add(node.val);
                for (int i = node.children.size() - 1; i >= 0; i--) { 
                    stk.push(node.children.get(i));
                }
            }
            return res;
        }
    }

# 3. 后序遍历 #

[Leetcode 590. N叉树的后序遍历][Leetcode 590. N]

**递归实现**：

class Solution { 
        public List<Integer> postorder(Node root) { 
            List<Integer> res = new ArrayList<>();
            helper(root, res);
            return res;
        }
    
        private void helper(Node root, List<Integer> res) { 
            if (root == null) { 
                return;
            }
    
            for (Node node : root.children) { 
                helper(node, res);
            }
            res.add(root.val);
        }
    }

**迭代实现**：

class Solution { 
        public List<Integer> postorder(Node root) { 
            if (root == null) { 
                return new ArrayList<>();
            }
    
            List<Integer> res = new ArrayList<>();
            Stack<Node> stk = new Stack<>();
            stk.push(root);
            while (!stk.isEmpty()) { 
                Node node = stk.pop();
                res.add(node.val);
                for (int i = 0; i < node.children.size(); i++) { 
                    stk.push(node.children.get(i));
                }
            }
            Collections.reverse(res);
            return res;
        }
    }

# 4. 层序遍历 #

[Leetcode 429. N叉树的层序遍历][Leetcode 429. N]

**递归实现**：

class Solution { 
        public List<List<Integer>> levelOrder(Node root) { 
            List<List<Integer>> res = new ArrayList<>();
            helper(root, 0, res);
            return res;
        }
    
        private void helper(Node root, int level, List<List<Integer>> res) { 
            if (root == null) { 
                return;
            }
            if (level == res.size()) { 
                res.add(new ArrayList<>());
            }
            res.get(level).add(root.val);
            for (Node node : root.children) { 
                helper(node, level + 1, res);
            }
        }
    }

**迭代实现**：

class Solution { 
        public List<List<Integer>> levelOrder(Node root) { 
            if (root == null) { 
                return new ArrayList<>();
            }
    
            List<List<Integer>> res = new ArrayList<>();
            Queue<Node> queue = new LinkedList<>();
            queue.add(root);
            while (!queue.isEmpty()) { 
                int n = queue.size();
                List<Integer> ans = new ArrayList<>();
                for (int i = 0; i < n; i++) { 
                    Node node = queue.remove();
                    ans.add(node.val);
                    for (int j = 0; j < node.children.size(); j++) { 
                        queue.add(node.children.get(j));
                    }
                }
                res.add(ans);
            }
            return res;
        }
    }

[Leetcode 589. N]: https://leetcode-cn.com/problems/n-ary-tree-preorder-traversal/
[Leetcode 590. N]: https://leetcode-cn.com/problems/n-ary-tree-postorder-traversal/
[Leetcode 429. N]: https://leetcode-cn.com/problems/n-ary-tree-level-order-traversal/