LeetCode每日一题（20200904）

原题地址：

思考过程：

bfs或者dfs。

代码实现：

public List<String> binaryTreePaths(TreeNode root) { return bfs(root); } public List<String> bfs(TreeNode root) { List<String> ans = new ArrayList<>(); if (root != null) { if (root.left == null && root.right == null) { ans.add(root.val + ""); return ans; } else { List<String> left = bfs(root.left); List<String> right = bfs(root.right); for (String s : left) { ans.add(root.val + "->" + s); } for (String s : right) { ans.add(root.val + "->" + s); } } } return ans; }

执行结果：

 

算法复杂度分析：

时间复杂度O(n²)

空间复杂度O(n²)

 

查看官方解法：

提供了dfs和bfs。

 

总结：

我爱周五

 

补充：

刷了几道leetcode上树相关的题目，链接和代码如下：

N叉树的前序遍历

public List<Integer> preorder(Node root) { List<Integer> ans = new ArrayList<>(); if (root != null) { ans.add(root.val); for (Node n : root.children) { ans.addAll(preorder(n)); } } return ans; }

递增顺序查找树

public TreeNode increasingBST(TreeNode root) { if (root == null) { return null; } if (root.left == null) { TreeNode ans = new TreeNode(); ans.val = root.val; ans.right = increasingBST(root.right); return ans; } else { TreeNode ans = increasingBST(root.left); TreeNode tem = ans; while (tem != null) { if (tem.right == null) { TreeNode t = new TreeNode(); t.val = root.val; t.right = increasingBST(root.right); tem.right = t; break; } tem = tem.right; } return ans; } }

路径总和

public boolean hasPathSum(TreeNode root, int sum) { if (root == null) { return false; } if (root.left == null && root.right == null) { return root.val == sum; } return hasPathSum(root.left, sum - root.val) || hasPathSum(root.right, sum - root.val); }