[LeetCode] 112. Path Sum

轉自LeetCode

Given a binary tree and a sum, determine if the tree has a root-to-leaf path such that adding up all the values along the path equals the given sum.

For example:
Given the below binary tree and sum = 22,

              5
             / \
            4   8
           /   / \
          11  13  4
         /  \      \
        7    2      1

return true, as there exist a root-to-leaf path 5->4->11->2 which sum is 22.

<Solution>

觀念和 Minimum Depth of Binary Tree 一樣，首先看 BFS 的解法

• 將 node 逐個丟到 queue 中，如果遇到 leaf node，檢查和是否等於要找的數，是的話就回傳 true，不是就繼續

code 如下

	/**
	* 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:
	bool hasPathSum(TreeNode* root, int sum) {
	if(!root) {
	return false;
	}
	queue<pair<TreeNode *,int>> nodeQue;
	nodeQue.push({root, root->val});
	while(!nodeQue.empty()) {
	TreeNode *tmpNode = nodeQue.front().first;
	int pathSum = nodeQue.front().second;
	if(!tmpNode->left && !tmpNode->right) {
	if(pathSum == sum) {
	return true;
	}
	}
	if(tmpNode->left) {
	nodeQue.push({tmpNode->left, pathSum + tmpNode->left->val});
	}
	if(tmpNode->right) {
	nodeQue.push({tmpNode->right, pathSum + tmpNode->right->val});
	}
	nodeQue.pop();
	}
	return false;
	}
	};

view raw pathSumOfBinaryTree_1.cpp hosted with ❤ by GitHub

當然，這個也有 recursive 的解法

• 空節點，回傳 false

• leaf node，檢查是否等於 sum 了

• node 還有任一子樹，繼續 recursive 下去。這邊只要有一個子樹為 true，整體就為 true

code 如下(參考資料)
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:
	bool hasPathSum(TreeNode* root, int sum) {
	if(!root) {
	return false;
	}
	//> leaf node
	if(!root->left && !root->right) {
	return root->val == sum;
	}
	//> check left subtree and right subtree
	return hasPathSum(root->left, sum - root->val) || hasPathSum(root->right, sum - root->val);
	}
	};

view raw pathSumOfBinaryTree_2.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 {
	fun hasPathSum(root: TreeNode?, targetSum: Int): Boolean {
	return when {
	root == null -> false
	root!!.left == null && root!!.right == null -> root!!.`val` == targetSum
	else -> {
	hasPathSum(root!!.left, targetSum - root!!.`val`)
	|| hasPathSum(root!!.right, targetSum - root!!.`val`)
	}
	}
	}
	}

view raw path_sum.kt hosted with ❤ by GitHub