[LeetCode] 257. Binary Tree Paths

轉自LeetCode

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"]

<Solution>

這題就用 recursive 來解

code 如下

Java

	/**
	* Definition for a binary tree node.
	* public class TreeNode {
	* int val;
	* TreeNode left;
	* TreeNode right;
	* TreeNode(int x) { val = x; }
	* }
	*/
	class Solution {
	public List<String> binaryTreePaths(TreeNode root) {
	LinkedList<String> ans = new LinkedList<>();
	if (root != null) {
	findPath(root, ans, "");
	}
	return ans;
	}
	private void findPath(TreeNode node, LinkedList<String> ans, String path) {
	if(node.left == null && node.right == null) {
	//>> leaf node
	ans.add(path + node.val);
	return;
	}
	if(node.left != null) {
	findPath(node.left, ans, path + node.val + "->");
	}
	if(node.right != null) {
	findPath(node.right, ans, path + node.val + "->");
	}
	}
	}

view raw binaryTreePaths.java hosted with ❤ by GitHub

C++

	/**
	* Definition for a binary tree node.
	* struct TreeNode {
	* int val;
	* TreeNode *left;
	* TreeNode *right;
	* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
	* };
	*/
	class Solution {
	public:
	vector<string> binaryTreePaths(TreeNode* root) {
	vector<string> ans;
	if(root) {
	findPaths(root, ans, "");
	}
	return ans;
	}
	void findPaths(TreeNode *node, vector<string> &ans, const string path) {
	if(!node->left && !node->right) {
	ans.push_back(path + to_string(node->val));
	return;
	}
	if(node->left) {
	findPaths(node->left, ans, path + to_string(node->val) + "->");
	}
	if(node->right) {
	findPaths(node->right, ans, path + to_string(node->val) + "->");
	}
	}
	};

view raw binaryTreePaths.cpp hosted with ❤ by GitHub

kotlin

	/**
	* Example:
	* var ti = TreeNode(5)
	* var v = ti.`val`
	* Definition for a binary tree node.
	* class TreeNode(var `val`: Int) {
	* var left: TreeNode? = null
	* var right: TreeNode? = null
	* }
	*/
	class Solution {
	var ans = mutableListOf<String>()
	fun binaryTreePaths(root: TreeNode?): List<String> {
	dfs(root, "")
	return ans
	}
	fun dfs(node: TreeNode?, path: String) {
	when {
	node == null -> return
	node!!.left == null && node!!.right == null -> {
	ans.add(path + "${node!!.`val`}")
	return
	}
	else ->{
	dfs(node!!.left, path + "${node!!.`val`}->")
	dfs(node!!.right, path + "${node!!.`val`}->")
	}
	}
	}
	}

view raw binary_tree_paths.kt hosted with ❤ by GitHub