[Microsoft面试]在二元树中找出和为某一值的所有路径
题目：输入一个整数和一棵二元树。从树的根结点开始往下访问一直到叶结点所经过的所有结点形成一条路径。打印出和与输入整数相等的所有路径。例如输入整数22 和如下二元树10/ \5 12/ \4 7则打印出两条路径：10, 12 和10, 5, 7。二元树节点的数据结构定义为：struct BinaryTreeNode // a node in the binary tree{int m_nValue; // value of nodeBinaryTreeNode *m_pLeft; // left child of nodeBinaryTreeNode *m_pRight; // right child of node}; Usebacktracking and recurison. We need a stack to help backtracking the path.struct TreeNode {int data;TreeNode * left;TreeNode * right;};voidprintPaths(TreeNode * root, int sum) {int path;helper(root, sum, path, 0);}voidhelper(TreeNode * root, int sum, int path[], int top) {path = root.data;sum -= root.data;if (root->left == NULL && root->right==NULL) { if (sum == 0) printPath(path, top);} else { if (root->left != NULL) helper(root->left, sum, path,top); if (root->right!=NULL) helper(root->right, sum, path,top);}top --;sum += root.data; //....}
页:
[1]