LeetCode 112. Path Sum 路径总和

Posted on | In

112. Path Sum 路径总和

题目描述

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.

Note: A leaf is a node with no children.

示例:

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.

解答1

第一种解法使用递归的方式，思想是在每次递归操作的时候都令sum = sum - 当前节点的值，这样如果递归到叶子节点sum为0，则说明存在这条路径，否则不存在。

代码1

1
2
3
4
5
6
7
8
9
class Solution {
public:
    bool hasPathSum(TreeNode* root, int sum) {
    	if (root == NULL) return false;
    	if (root->left == NULL && root->right == NULL && sum - root->val == 0) return true;
    	return hasPathSum(root->left, sum - root->val) || hasPathSum(root->right, sum - root->val);
    }

};

解答2

第二种解法是利用树的先序遍历。

对树进行先序遍历，在遍历的同时将当前节点的值加入路径和中，若遍历到叶子节点时路径和等于sum，则返回true，说明路径存在。

若遍历到叶子节点发现路径和不等于sum，就把该节点的值从路径和中删掉。

注意在遍历过程中，要判断当前节点的前一个节点是否被访问过，用pre变量实现，详见代码。

代码2

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
class Solution {
public:
    bool hasPathSum(TreeNode* root, int sum) {
        stack<TreeNode *> s;
        int total = 0;
        TreeNode *pre = NULL, *cur = root;
        while (cur || !s.empty()) {
        	while (cur) {
        		s.push(cur);
        		total += cur->val;
        		cur = cur->left;

        	}
        	cur = s.top();
        	if (cur->left == NULL && cur->right == NULL && sum == total);
        		return true;
        	//判断当前节点是否有右子树，并且右子树没有被访问过。
        	if (cur->right && pre != cur->right) {
        		cur = cur->right;
        		else {
        			//代表之前的节点被访问过
        			pre = cur;
        			s.pop();
        			total -= cur->val;
        			cur = NULL;
        		}

        	}
        } 
        return false;
    }
};