本文共 1065 字,大约阅读时间需要 3 分钟。
Given a binary tree, return the preorder traversal of its nodes’ values.
For example:
Given binary tree {1,#,2,3},1
\ 2 / 3return [1,2,3].
Note: Recursive solution is trivial, could you do it iteratively?
题目要求对二叉树进行非递归的前序遍历,所谓前序遍历即,先访问根节点、再访问左子树、然后是右子树。通常采用递归的方法,题目要求采用非递归的方法实现。算法如下:
1)如果根节点非空,将根节点加入到栈中。
2)如果栈不空,弹出出栈顶节点,将其值加加入到数组中。
如果该节点的右子树不为空,将右子节点加入栈中。 如果左子节点不为空,将左子节点加入栈中。
3)重复第二步,直到栈空。
代码如下:class Solution {public: vector preorderTraversal(TreeNode* root) { vector result; stack< TreeNode *> node_stack; if (root != NULL) { node_stack.push(root); } while (!node_stack.empty()) { TreeNode * tmpNode = node_stack.top(); node_stack.pop(); result.push_back(tmpNode->val); if (tmpNode->right) { node_stack.push(tmpNode->right); } if (tmpNode->left) { node_stack.push(tmpNode->left); } } return result; }};
转载地址:http://gfxti.baihongyu.com/