leetcode 129. Sum Root to Leaf Numbers

古城微笑少年丶 2022-07-29 08:58 143阅读 0赞

Given a binary tree containing digits from `0-9` only, each root-to-leaf path could represent a number.

An example is the root-to-leaf path `1->2->3` which represents the number `123`.

Find the total sum of all root-to-leaf numbers.

For example,

1
       / \
      2   3

The root-to-leaf path `1->2` represents the number `12`.  
The root-to-leaf path `1->3` represents the number `13`.

Return the sum = 12 + 13 = `25`.

class Solution {
    	long long int vecnodetonum(vector<pair<TreeNode*, bool> >&quene)
    	{
    		long long int re = 0;
    		for (int i = 0; i < quene.size(); i++)
    			re += ((long long int)(quene[i].first->val))*powl(10, quene.size() - 1 - i);
    		return re;
    	}
    public:
    	int sumNumbers(TreeNode* root) {
    		if (root == NULL)
    			return 0;
    		long long int sum = 0;
    		vector<pair<TreeNode*, bool> >quene;//bool标识当前节点右子树是否被访问过
    		quene.push_back(pair<TreeNode*, bool>(root, false));
    		bool f = true;
    		while (!quene.empty())
    		{
    			if (f&&quene.back().first->left != NULL)
    				quene.push_back(pair<TreeNode*, bool>(quene.back().first->left, false));
    			else if (quene.back().first->right != NULL)
    			{
    
    				if (quene.back().second == false)
    				{
    					f = true;
    					quene.back().second = true;
    					quene.push_back(pair<TreeNode*, bool>(quene.back().first->right, false));
    				}
    				else
    					quene.pop_back();
    			}
    			else
    			{
    				if (quene.back().first->left == NULL
    					&&quene.back().first->right == NULL)
    					sum += vecnodetonum(quene);
    				quene.pop_back(); f = false;
    			}
    		}
    		return sum;
    	}
    };

accepted