微软等数据结构与算法面试100题 第四题

发布时间:2016-12-10 13:02:30 编辑:www.fx114.net 分享查询网我要评论
本篇文章主要介绍了"微软等数据结构与算法面试100题 第四题",主要涉及到微软等数据结构与算法面试100题 第四题方面的内容,对于微软等数据结构与算法面试100题 第四题感兴趣的同学可以参考一下。

第四题 题目:输入一个整数和一棵二元树。 从树的根结点开始往下访问一直到叶结点所经过的所有结点形成一条路径。 打印出和与输入整数相等的所有路径。 例如 输入整数22和如下二元树   10    / \    5  12    /   \   4     7 则打印出两条路径:10, 12和10, 5, 7。 当访问到某一结点时,把该结点添加到路径上,并累加当前结点的值。 如果当前结点为叶结点并且当前路径的和刚好等于输入的整数,则当前的路径符合要求,我们把它打印出来 。 如果当前结点不是叶结点,则继续访问它的子结点。当前结点访问结束后,递归函数将自动回到父结点。 因此我们在函数退出之前要在路径上删除当前结点并减去当前结点的值, 以确保返回父结点时路径刚好是根结点到父结点的路径。 我们不难看出保存路径的数据结构实际上是一个栈结构,因为路径要与递归调用状态一致, 而递归调用本质就是一个压栈和出栈的过程。 void FindPath ( BinaryTreeNode* pTreeNode, // a node of binary tree int expectedSum, // the expected sum std::vector<int>& path, // a path from root to current node int& currentSum // the sum of path ) { if(!pTreeNode) return; currentSum += pTreeNode->m_nValue; path.push_back(pTreeNode->m_nValue); // if the node is a leaf, and the sum is same as pre-defined, // the path is what we want. print the path bool isLeaf = (!pTreeNode->m_pLeft && !pTreeNode->m_pRight); if(currentSum == expectedSum && isLeaf) { std::vector<int>::iterator iter = path.begin(); for(; iter != path.end(); ++ iter) std::cout << *iter << '/t'; std::cout << std::endl; } // if the node is not a leaf, goto its children if(pTreeNode->m_pLeft) FindPath(pTreeNode->m_pLeft, expectedSum, path, currentSum); if(pTreeNode->m_pRight) FindPath(pTreeNode->m_pRight, expectedSum, path, currentSum); // when we finish visiting a node and return to its parent node, // we should delete this node from the path and // minus the node's value from the current sum currentSum -= pTreeNode->m_nValue; path.pop_back(); } 方法二: #include<iostream> #include<queue> #include<stack> using namespace std; typedef struct NodeBinaryTree { int value; NodeBinaryTree * nodeLeft; NodeBinaryTree * nodeRight; }NodeBinaryTree; class BinaryTree { private: NodeBinaryTree * root; stack<int> Path; public: BinaryTree(); //~BSTree(); 这个地方需要递归delete所有节点 NodeBinaryTree * Root(){return root;} void addNodeBSTree(const int item); void inOrder(NodeBinaryTree * root); void inOrderStack(const int item); }; BinaryTree::BinaryTree() { root = NULL; } void BinaryTree::addNodeBSTree(const int item) { //这个地方写代码的时候使用了广度优先的插入节点,当时不知道怎么想的就写了这个 //与本题关系不大,可以直接忽略 if(NULL==root) { NodeBinaryTree * node2add = new NodeBinaryTree(); node2add->value = item; node2add->nodeLeft = NULL; node2add->nodeRight = NULL; root = node2add; } else { //BinaryTree的节点的插入采用的是广度优先的插入方式,因此这里我们定义了一个队列,直接采用了STL里面的队列 using std::queue; queue<NodeBinaryTree *> aQueue; NodeBinaryTree * pointer = root; if(pointer) aQueue.push(pointer); while(!aQueue.empty()) { pointer = aQueue.front(); aQueue.pop(); if(NULL!=pointer->nodeLeft && NULL!=pointer->nodeRight){//为什么书上这个地方有括号 aQueue.push(pointer->nodeLeft); aQueue.push(pointer->nodeRight); } else if(NULL!=pointer->nodeLeft && NULL==pointer->nodeRight) { //找到当前的没有右子树的点,将待加入的点插入的右子树 NodeBinaryTree * node2add = new NodeBinaryTree(); pointer->nodeRight = node2add; node2add->value = item; node2add->nodeLeft = NULL; node2add->nodeRight = NULL; break; } else //说明是左子树是NULL { NodeBinaryTree * node2add = new NodeBinaryTree(); pointer->nodeLeft = node2add; node2add->value = item; node2add->nodeLeft = NULL; node2add->nodeRight = NULL; break; } } } } void BinaryTree::inOrder(NodeBinaryTree * root) { if(NULL!=root) { inOrder(root->nodeLeft); cout<<root->value<<" "; inOrder(root->nodeRight); } } void BinaryTree::inOrderStack(const int item) { cout<<"the expected sum of the path is "<<item<<endl; NodeBinaryTree * root = this->root; //非递归周游二叉树 enum Tags{Left,Right}; struct StackElement { NodeBinaryTree * pointer; Tags tag; }; StackElement element; StackElement elementCopy; stack<StackElement> aStack; stack<StackElement> aCopyStack; NodeBinaryTree * pointer; if(NULL==root){return;} else pointer = root; int sumValue = 0; int nodeValue; while(true){ while(NULL!=pointer) { element.pointer = pointer; element.tag = Left; aStack.push(element); sumValue = sumValue + element.pointer->value; pointer = pointer->nodeLeft; } element = aStack.top(); if(element.tag==Right && NULL==element.pointer->nodeLeft&& NULL== element.pointer->nodeRight && item==sumValue) { //因为每次考虑Tag的时候考虑了right和left 所以要使不使用element.tag==Right判断条件会打印两遍 //若找到了路径 //输出栈中的元素 然后再把栈重新组织成原来的样子 while(!aStack.empty()){ elementCopy = aStack.top(); aStack.pop(); aCopyStack.push(elementCopy); } while(!aCopyStack.empty()){ elementCopy = aCopyStack.top(); aCopyStack.pop(); aStack.push(elementCopy); cout<<elementCopy.pointer->value<<" "; } cout<<endl; } aStack.pop(); sumValue = sumValue - element.pointer->value; pointer = element.pointer; //从右子树回来 while(element.tag==Right){ if(aStack.empty()) return; else { element = aStack.top(); aStack.pop(); sumValue = sumValue - element.pointer->value; pointer = element.pointer; } } //从左子树回来 element.tag = Right; aStack.push(element); sumValue = sumValue + element.pointer->value; pointer = pointer->nodeRight; } } int main() { BinaryTree a; a.addNodeBSTree(1); a.addNodeBSTree(2); a.addNodeBSTree(3); a.addNodeBSTree(4); a.addNodeBSTree(6); a.addNodeBSTree(5); a.addNodeBSTree(7); NodeBinaryTree * head = a.Root(); //test inorder a.inOrder(head); cout<<endl; a.inOrderStack(9); return 0; }

上一篇:
下一篇:关于手动书写json 格式

相关文章

相关评论