[LeetCode] 257. Binary Tree Paths 二叉树路径
2023-09-27 14:28:37 时间
Given a binary tree, return all root-to-leaf paths.
For example, given the following binary tree:
1 / \ 2 3 \ 5
All root-to-leaf paths are:
["1->2->5", "1->3"]
给一个二叉树,返回所有根到叶节点的路径。
Java:
/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */ public class Solution { public List<String> binaryTreePaths(TreeNode root) { List<String> list = new ArrayList<>(); binaryTreePathsHelper(root, list, new String()); return list; } public void binaryTreePathsHelper(TreeNode root, List<String> list, String string) { if (root == null) { return; } if (root.left == null && root.right == null) { string = string + root.val; list.add(string); return; } binaryTreePathsHelper(root.left, list, string + root.val + "->"); binaryTreePathsHelper(root.right, list, string + root.val + "->"); } }
Python:
class Solution: # @param {TreeNode} root # @return {string[]} def binaryTreePaths(self, root): result, path = [], [] self.binaryTreePathsRecu(root, path, result) return result def binaryTreePathsRecu(self, node, path, result): if node is None: return if node.left is node.right is None: ans = "" for n in path: ans += str(n.val) + "->" result.append(ans + str(node.val)) if node.left: path.append(node) self.binaryTreePathsRecu(node.left, path, result) path.pop() if node.right: path.append(node) self.binaryTreePathsRecu(node.right, path, result) path.pop()
C++: DFS
class Solution { public: vector<string> binaryTreePaths(TreeNode* root) { vector<string> res; if (root) dfs(root, "", res); return res; } void dfs(TreeNode *root, string out, vector<string> &res) { out += to_string(root->val); if (!root->left && !root->right) res.push_back(out); else { if (root->left) dfs(root->left, out + "->", res); if (root->right) dfs(root->right, out + "->", res); } } };
C++:
class Solution { public: vector<string> binaryTreePaths(TreeNode* root) { if (!root) return {}; if (!root->left && !root->right) return {to_string(root->val)}; vector<string> left = binaryTreePaths(root->left); vector<string> right = binaryTreePaths(root->right); left.insert(left.end(), right.begin(), right.end()); for (auto &a : left) { a = to_string(root->val) + "->" + a; } return left; } };
类似题目:
[LeetCode] 113. Path Sum II 路径和 II
[LeetCode] 437. Path Sum III 路径和 III
All LeetCode Questions List 题目汇总
相关文章
- Leetcode: Minimum Unique Word Abbreviation
- Leetcode: Power of Three
- Leetcode: Paint Fence
- LeetCode-1.两数之和
- 【Leetcode】110. 平衡二叉树(简单)
- 【Leetcode】111. 二叉树的最小深度
- LeetCode数据结构_C语言题解系列-数组
- 110、【树与二叉树】leetcode ——450. 删除二叉搜索树中的节点:递归法+迭代法(C++版本)
- 100、【树与二叉树】leetcode ——105. 从前序与中序遍历序列构造二叉树+106. 从中序与后序遍历序列构造二叉树(C++版本)
- 98、【树与二叉树】leetcode ——112. 路径总和:5行精简代码回溯法[带剪枝]+迭代法(C++版本)
- 93、【树与二叉树】leetcode ——222. 完全二叉树的节点个数:普通二叉树求法+完全二叉树性质求法(C++版本)
- 【leetcode】日积月累,每日一题--206. 反转链表(DayDayUp 13)
- 【Leetcode】101:对称二叉树(Python)
- [LeetCode] 1104. Path In Zigzag Labelled Binary Tree 之字形二叉树路径
- [LeetCode] 894. All Possible Full Binary Trees 所有可能的满二叉树
- [LeetCode] Arithmetic Slices II - Subsequence 算数切片之二 - 子序列
- [LeetCode] Bulls and Cows 公母牛游戏
- [LeetCode] 222. Count Complete Tree Nodes 求完全二叉树的节点个数
- [LeetCode] 43. Multiply Strings 字符串相乘
- [LeetCode] 94. Binary Tree Inorder Traversal 二叉树的中序遍历
- [LeetCode] 124. Binary Tree Maximum Path Sum 求二叉树的最大路径和
- [LeetCode] 113. Path Sum II 二叉树路径之和之二
- LeetCode合并二叉树
- leetcode 94. Binary Tree Inorder Traversal 二叉树的中序遍历(中等)