开放原子开发者工作坊

题目：

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. 

思路：类似于二叉树的遍历，遍历的过过程中要记录节点数据，并且转化为sum（越接近叶子节点的节点的数值离各位最近，因为叶子节点是个位数，叶子节点的根节点是十位数。。。根root节点更高位），要标记已经计算过的节点（将值赋值为-1），叶子节点遍历过回溯到根节点，继续搜索。

#include<iostream>
#include<stack>
using namespace std;
//二叉树的定义 
struct TreeNode {
      int val;
      TreeNode *left;
      TreeNode *right;
      TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};
int sumNumbers(TreeNode* root)
{
      TreeNode* p = root;
      if(p==NULL) return 0; 
      //栈，搜索节点时，存储节点 
      stack<TreeNode*> s;
      //根到每一个叶子节点的和 
      int sum = 0;
      //sum 之和 
      int result = 0;
      //最左下的节点（不一定是叶子） 
      while(p!=NULL)
      {
            s.push(p);
            sum = sum * 10 + p->val;
            p = p->left;
      }
      while(!s.empty())
      {
            p = s.top();
            //不是叶子节点，且没遍历过 
            if(p->right!=NULL&&p->right->val!=-1)
            {
                p = p->right;
                s.push(p);
                sum = sum*10 + p->val;
                while(p->left!=NULL)
                {
                   p = p->left;
                   s.push(p);
                   sum = sum*10 + p->val;
                }
            }
            else if(p->left==NULL && p->right == NULL)//叶子节点 
            {
                   result += sum;
                   //回溯到该节点的根 
                   s.pop();
                   sum/=10;
                   //标记 
                   p->val = -1;
            }
            //不是叶子节点，且已遍历过 
            else if((p->left==NULL&&p->right!=NULL&&p->right->val==-1)||(p->right==NULL&&p->left!=NULL&&p->left->val==-1)
                    ||(p->left!=NULL&&p->right!=NULL&&p->left->val==-1&&p->right->val==-1))
                    {
                       s.pop();
                       sum/=10;
                       //标记
                       p->val = -1; 
                    }
      }
      return result;
}
int main(void)
{
    TreeNode* root = new TreeNode(9);
    TreeNode* p2 = new TreeNode(2);
    TreeNode* p3 = new TreeNode(3);
    TreeNode* p4 = new TreeNode(4);
    TreeNode* p5 = new TreeNode(5);
    TreeNode* p6 = new TreeNode(6);
    TreeNode* p7 = new TreeNode(7);
    
    root->left = p2;
    root->right = p3;
    
    p2->left = p4;
    p2->right = p5;
    
    p3->left = p6;
    p3->right = p7;
    
    int a = sumNumbers(root);
    
    cout<<a<<endl;
    delete(root);
    delete(p2);
    delete(p3);
    delete(p4);
    delete(p5);
    delete(p6);
    delete(p7);
    system("pause");
    return 0;
}

可以找一个比较“变态”的树，走一遍程序，思路就会很清楚。