sta logs 结束 nod 递归实现 inorder count site
二叉树的遍历有前序遍历、中序遍历、后序遍历、层次遍历等,笔者在这里总结一下各种遍历的实现。
一. 前序遍历。
前序遍历访问节点顺序为:根节点 -> 左子节点 -> 右子节点。
递归实现如下:
- void preorder(TreeNode* root, vector<int>& nodes) {
- if (!root) return;
- nodes.push_back(root -> val);
- preorder(root -> left, nodes);
- preorder(root -> right, nodes);
- }
- vector<int> preorderTraversal(TreeNode* root) {
- vector<int> nodes;
- preorder(root, nodes);
- return nodes;
- }
非递归实现 (使用栈) 如下:
对于任一结点 P:
①访问结点 P,并将结点 P 入栈;
②判断结点 P 的左孩子是否为空,若为空,则取栈顶结点并进行出栈操作,并将栈顶结点的右孩子置为当前的结点 P,循环至①; 若不为空,则将 P 的左孩子置为当前的结点 P;
③直到 P 为 NULL 并且栈为空,则遍历结束。
- vector<int> preorderTraversal(TreeNode *root) {
- vector<int> v;
- if (root == NULL) return v;
- stack<TreeNode*> s;
- TreeNode* temp = root;
- while (temp != NULL || !s.empty()) {
- while (temp != NULL) {
- v.push_back(temp->val);
- s.push(temp);
- temp = temp->left;
- }
- if (!s.empty()) {
- temp = s.top();
- s.pop();
- temp = temp->right;
- }
- }
- return v;
- }
二. 中序遍历。
中序遍历访问节点顺序为:左子节点 -> 根节点 -> 右子节点。
递归实现如下:
- void inorder(TreeNode* root, vector<int>& nodes) {
- if (!root) return;
- inorder(root -> left, nodes);
- nodes.push_back(root -> val);
- inorder(root -> right, nodes);
- }
- vector<int> inorderTraversal(TreeNode* root) {
- vector<int> nodes;
- inorder(root, nodes);
- return nodes;
- }
非递归实现 (使用栈) 如下:
对于任一结点 P,
①若其左孩子不为空,则将 P 入栈并将 P 的左孩子置为当前的 P,然后对当前结点 P 再进行相同的处理;
②若其左孩子为空,则取栈顶元素并进行出栈操作,访问该栈顶结点,然后将当前的 P 置为栈顶结点的右孩子;
③直到 P 为 NULL 并且栈为空则遍历结束
- vector<int> inorderTraversal(TreeNode *root) {
- vector<int> v;
- if (root == NULL) return v;
- stack<TreeNode*> s;
- TreeNode *temp = root;
- while (temp != NULL || !s.empty()) {
- while (temp != NULL) {
- s.push(temp);
- temp = temp->left;
- }
- if (!s.empty()) {
- temp = s.top();
- s.pop();
- v.push_back(temp->val);
- temp = temp->right;
- }
- }
- return v;
- }
三. 后序遍历。
后序遍历访问节点顺序为:左子节点 -> 右子节点 -> 根节点。
递归实现如下:
- void postorder(TreeNode* root, vector<int>& nodes) {
- if (!root) return;
- postorder(root -> left, nodes);
- postorder(root -> right, nodes);
- nodes.push_back(root -> val);
- }
- vector<int> postorderTraversal(TreeNode* root) {
- vector<int> nodes;
- postorder(root, nodes);
- return nodes;
- }
非递归实现 (使用栈) 如下:
- vector<int> postorderTraversal(TreeNode *root) {
- vector<int> v;
- stack<TreeNode*> s;
- TreeNode * curr = root;
- TreeNode * previsited = NULL;
- while (curr != NULL || !s.empty()) {
- while (curr != NULL) {
- s.push(curr);
- curr = curr->left;
- }
- curr = s.top();
- // 当前节点的右孩子如果为空或者已经被访问,则访问当前节点
- if (curr->right == NULL || curr->right == previsited) {
- v.push_back(curr->val);
- previsited = curr;
- s.pop();
- curr = NULL;
- }
- else curr = curr->right; //否则访问右孩子
- }
- return v;
- }
四. 层次遍历。
使用队列:
- vector<vector<int>> levelOrder(TreeNode *root) {
- queue<TreeNode*> q;
- int count = 0;
- vector<int> v;
- vector<vector<int>> v2;
- if (root == NULL) return v2;
- q.push(root);
- count++;
- int count2 = 1;
- while (!q.empty()) {
- count = count2;
- count2 = 0;
- v.clear();
- for (int i = 0; i < count; i++) {
- TreeNode * top = q.front();
- v.push_back(top->val);
- if (top->left != NULL) {
- q.push(top->left);
- count2++;
- }
- if (top->right != NULL) {
- q.push(top->right);
- count2++;
- }
- q.pop();
- }
- v2.push_back(v);
- }
- return v2;
- }
二叉树的前序、中序、后序、层次遍历的递归与非递归实现
来源: http://www.bubuko.com/infodetail-2135691.html