今天遇到一个没有写出来的算法题，记录一下。
如下：要求我补充完整printCategory()和buildTree()两个函数。
printCategory()函数负责打印
buildTree()负责构造树节点
public class Interview001 { static class Category { /** * 分类id */ Integer id; /** * 名称 */ String name; /** * 父级分类id */ Integer parentId; static Category create(Integer id, String name, Integer parentId) { Category category = new Category(); category.id = id; category.name = name; category.parentId = parentId; return category; } } static class TreeNode { /** * 节点数据 */ Category data; /** * 子节点列表 */ List<TreeNode> childNodes; /** * 父节点 */ TreeNode parentNode; static TreeNode create(Category data) { TreeNode node = new TreeNode(); node.data = data; node.childNodes = new ArrayList<>(); return node; } } public static void main(String[] args) { Interview001 interview001 = new Interview001(); List<Category> categoryList = new ArrayList<>(); categoryList.add(Category.create(0, "女装", null)); categoryList.add(Category.create(1, "上装", 0)); categoryList.add(Category.create(3, "衬衫", 1)); categoryList.add(Category.create(4, "短袖衬衫", 3)); categoryList.add(Category.create(5, "长袖衬衫", 3)); categoryList.add(Category.create(6, "T恤", 1)); categoryList.add(Category.create(7, "长袖T", 6)); categoryList.add(Category.create(8, "短袖T", 6)); categoryList.add(Category.create(9, "毛衣", 1)); categoryList.add(Category.create(10, "外套", 1)); categoryList.add(Category.create(11, "下装", 0)); categoryList.add(Category.create(12, "裙子", 11)); categoryList.add(Category.create(13, "短裙", 12)); categoryList.add(Category.create(14, "长裙", 12)); categoryList.add(Category.create(15, "裤子", 11)); categoryList.add(Category.create(16, "长裤", 15)); TreeNode root = interview001.buildTree(categoryList); interview001.printCategory(root); } /** * 按如下格式打印出分类树: * 女装 * 上装 * 衬衫 * 短袖衬衫 * 长袖衬衫 * T恤 * 长袖T * 短袖T * 毛衣 * 外套 * 下装 * 裙子 * 短裙 * 长裙 * 裤子 * 长裤 */ // TODO: 实现打印分类树逻辑 private void printCategory(TreeNode root) { } // TODO: 构建分类树 private TreeNode buildTree(List<Category> categoryList) { } }
其实这题考察的点也很明显，深度优先遍历。通常而言，树的题目都是会考察深度优先遍历或者广度优先遍历的，然后深度优先遍历或者广度优先遍历通常又会用到递归的思想去做。
- 构造树
- 用一个Map存储对应的id和TreeNode
- 遍历传进来的List categoryList ，如果对于Category的父节点为null的那它肯定是根节点。
- 根据HashMap去得到其父节点，如果父节点不为null，那就把self.parentNode 指向其父节点，然后根据map得到的父节点来把当前节点添加进它的子节点
- 最后返回根节点就可以了
我在做这个题的时候也是用HashMap存储的id和TreeNode,但是后面我总是想着把root移到下一层去，回不来。这里认知错误，其实对于这种构造树的情况，通常是root不用动，每次遇到子节点的时候，把子节点和父节点的相关信息通过map就可以得到了。
最后贴一下大佬写的
import java.util.ArrayList; import java.util.HashMap; import java.util.List; import java.util.Map; public class Interview001 { static class Category { /** * 分类id */ Integer id; /** * 名称 */ String name; /** * 父级分类id */ Integer parentId; static Category create(Integer id, String name, Integer parentId) { Category category = new Category(); category.id = id; category.name = name; category.parentId = parentId; return category; } } static class TreeNode { /** * 节点数据 */ Category data; /** * 子节点列表 */ List<TreeNode> childNodes; /** * 父节点 */ TreeNode parentNode; static TreeNode create(Category data) { TreeNode node = new TreeNode(); node.data = data; node.childNodes = new ArrayList<>(); return node; } } public static void main(String[] args) { Interview001 interview001 = new Interview001(); List<Category> categoryList = new ArrayList<>(); categoryList.add(Category.create(0, "女装", null)); categoryList.add(Category.create(1, "上装", 0)); categoryList.add(Category.create(3, "衬衫", 1)); categoryList.add(Category.create(4, "短袖衬衫", 3)); categoryList.add(Category.create(5, "长袖衬衫", 3)); categoryList.add(Category.create(6, "T恤", 1)); categoryList.add(Category.create(7, "长袖T", 6)); categoryList.add(Category.create(8, "短袖T", 6)); categoryList.add(Category.create(9, "毛衣", 1)); categoryList.add(Category.create(10, "外套", 1)); categoryList.add(Category.create(11, "下装", 0)); categoryList.add(Category.create(12, "裙子", 11)); categoryList.add(Category.create(13, "短裙", 12)); categoryList.add(Category.create(14, "长裙", 12)); categoryList.add(Category.create(15, "裤子", 11)); categoryList.add(Category.create(16, "长裤", 15)); TreeNode root = interview001.buildTree(categoryList); interview001.printCategory(root); } /** * 按如下格式打印出分类树: * 女装 * 上装 * 衬衫 * 短袖衬衫 * 长袖衬衫 * T恤 * 长袖T * 短袖T * 毛衣 * 外套 * 下装 * 裙子 * 短裙 * 长裙 * 裤子 * 长裤 */ // TODO: 实现打印分类树逻辑 private void printCategory(TreeNode root) { this.dfs(root, 0); } private void dfs(TreeNode node, Integer level){ String prefix = new String(new char[level]).replace("\0", "\t"); if (node != null){ System.out.print(prefix); System.out.println(node.data.name); } for (TreeNode child : node.childNodes){ this.dfs(child, level+1); } } // TODO: 构建分类树 private TreeNode buildTree(List<Category> categoryList) { Map<Integer, TreeNode> nodeMap = new HashMap(); TreeNode root = null; for (Category category: categoryList) { TreeNode self = TreeNode.create(category); nodeMap.put(category.id, self); if (category.parentId==null){ root = self; continue; } TreeNode parent = nodeMap.get(category.parentId); if (parent!=null){ self.parentNode = parent; parent.childNodes.add(self); } } return root; } }
