题目链接
题目描述
- 给定一棵二叉树，它的结点的值都在0-9之间，每一条从根结点到叶子结点的路径都可以代表一个数字。比如如果某条路径是1->2->3，那么它代表的数字则是123。要求找出给定的二叉树的所有上述路径，返回这些路径代表的数字之和。
解题思路
- 根据题目中对路径的描述，我们可以知道每条路径代表的数字中，根结点的数字位于最左边，叶子结点的数字位于最右边，每个结点的数字都位于它的子结点左边以及它的父结点右边，也就是说每个结点的进位都比它的子结点多一位，比它的父结点少一位。
- 本题的解法：
- 从根结点的开始遍历。
- 遍历结点的时候，将之前的数字进一位（乘以10），再加上当前结点的数字，就是从根结点到当前结点为止的子路径代表的数字。
- 若当前遍历的结点是叶子结点（没有任何子结点），那么当前子路径即是所求的路径之一，将上一步计算得到的数字加到总和之中。
- 若当前遍历的结点不是叶子结点，则继续遍历它的子结点，将之前计算的数字传递下去。
- 遍历完所有结点之后，所求的总和也就计算完成了。
- 这个解法对每个结点都访问了一次，因此时间复杂度为O(n)，n为二叉树的结点总数。
C++代码
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
#include <stack>
class Solution {
public:
int kthSmallest(TreeNode* root, int k) {
int num = 0;
stack<TreeNode*> s;
s.push(root);
TreeNode* node = root;
while (node || !s.empty()) {
if (node && node->left) {
s.push(node->left);
node = node->left;
continue;
}
node = s.top();
if (++num == k) {
return node->val;
}
s.pop();
if (node->right) {
s.push(node->right);
}
node = node->right;
}
return root->val;
}
};