上海做网站培训班,全屏企业网站,基于ipv6的网站开发,云南建设学院的网站题目描述 题目分析
更加地觉得编程重要的不在于如何写代码#xff0c;用什么具体的技巧#xff0c;编码本身只是一种将思维呈现的方式#xff0c;但是如果思维是不清晰的#xff0c;那么就算懂得再多的编码的奇技淫巧也是没有什么帮助的。相反#xff0c;如果有一个清晰的…题目描述 题目分析
更加地觉得编程重要的不在于如何写代码用什么具体的技巧编码本身只是一种将思维呈现的方式但是如果思维是不清晰的那么就算懂得再多的编码的奇技淫巧也是没有什么帮助的。相反如果有一个清晰的思路便能很轻松的写出优雅的代码。最近在看《编程大师访谈》感觉很多大师都提到的一个思想编程最重要的是数学而不是代码本身。他们觉得本科教育完全不应该接触计算机而是应该学习数学、历史等知识。我刚进大学的时候觉得学习高数、大学物理没有丝毫意义现在慢慢觉得那些知识对思维的训练的重要程度比什么所谓的专业课重要的多。
大概花了二十分钟做这道题觉得最后的实现方式还是比较优美的。
其实题目要求的就是二叉搜索树的中序遍历但是显然不能使用递归的方式因此一个栈是必须的用一个指针指向当前返回的值。
通过对中序遍历的模拟可以发现任何时候这个指针都在指向一个子树的最左侧的节点。而下一个位置在其右子树的最左侧节点。如果没有右子树则返回栈中的下一个节点该节点是当前节点最近的没有访问过的祖先。
总结一下对于当前节点我们不用访问他的左子树因为它的左子树要么为空要么已经访问我们会访问他的右子树如果没有右子树则返回栈中的下一个节点。如果栈为空则返回空指针表示遍历结束
问题在于我们什么时候入栈呢正是在搜索一个子树最左侧节点的时候将其路径上的节点全部入栈记录当前节点的所有祖先最后再依次访问。
class BSTIterator {
public:BSTIterator(TreeNode* root) {iter find_min(root);}int next() {int ret iter-val;if (iter-right ! nullptr) {iter find_min(iter-right);} else {if (!stk.empty()) {iter stk.top();stk.pop();} else {iter nullptr;}}return ret;}bool hasNext() {return iter ! nullptr;}
private:stackTreeNode * stk; //保存根节点栈TreeNode *iter;TreeNode *find_min(TreeNode *root) {if (root nullptr) return root;while (root-left ! nullptr) {stk.push(root);root root-left;}return root;}
};
