首页 > 代码库 > 37. Binary Tree Zigzag Level Order Traversal && Binary Tree Inorder Traversal
37. Binary Tree Zigzag Level Order Traversal && Binary Tree Inorder Traversal
Binary Tree Zigzag Level Order Traversal
Given a binary tree, return the zigzag level order traversal of its nodes‘ values. (ie, from left to right, then right to left for the next level and alternate between).
For example: Given binary tree {3,9,20,#,#,15,7},
3 / 9 20 / 15 7
return its zigzag level order traversal as:
[ [3], [20,9], [15,7]]
思路： 使用两个队列（一个可以顺序读，所以用vector模拟），每个队列放一层结点。
/** * Definition for binary tree * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode(int x) : val(x), left(NULL), right(NULL) {} * }; */void getQue1(vector<TreeNode*> &q1, queue<TreeNode*> &q2, vector<vector<int> > &vec) { while(!q2.empty()) { TreeNode *p = q2.front(); q2.pop(); if(p->left) q1.push_back(p->left); if(p->right) q1.push_back(p->right); } if(q1.size() == 0) return; vector<int> vec2; for(int i = q1.size()-1; i >= 0; --i) vec2.push_back(q1[i]->val); vec.push_back(vec2);}void getQue2(queue<TreeNode*> &q2, vector<TreeNode*> &q1, vector<vector<int> > &vec) { if(q1.size() == 0) return; vector<int> vec2; for(int i = 0; i < q1.size(); ++i) { if(q1[i]->left) { q2.push(q1[i]->left); vec2.push_back(q1[i]->left->val); } if(q1[i]->right) { q2.push(q1[i]->right); vec2.push_back(q1[i]->right->val); } } if(vec2.size()) vec.push_back(vec2); q1.clear();}class Solution {public: vector<vector<int> > zigzagLevelOrder(TreeNode *root) { vector<vector<int> > vec; if(root == NULL) return vec; queue<TreeNode*> q2; vector<TreeNode*> q1; q2.push(root); vec.push_back(vector<int>(1, root->val)); while(!q2.empty()) { getQue1(q1, q2, vec); getQue2(q2, q1, vec); } return vec; }};
Binary Tree Inorder Traversal
OJ: https://oj.leetcode.com/problems/binary-tree-inorder-traversal/
Given a binary tree, return the inorder traversal of its nodes‘ values.
For example: Given binary tree {1,#,2,3},
1 2 / 3
return [1,3,2].
Note: Recursive solution is trivial, could you do it iteratively?
题解： 两种方法： 1. 使用栈: O(n) Time, O(n) Space。 2. Morris traversal (构造线索树), O(n) Time, O(1) Space.
1. 使用栈
/** * Definition for binary tree * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode(int x) : val(x), left(NULL), right(NULL) {} * }; */class Solution {public: vector<int> inorderTraversal(TreeNode *root) { vector<int> vec; if(root == NULL) return vec; TreeNode *p = root; stack<TreeNode *> st; st.push(p); while(p->left) { p = p->left; st.push(p); } while(!st.empty()) { TreeNode *q = st.top(); st.pop(); vec.push_back(q->val); if(q->right) { q = q->right; st.push(q); while(q->left) { q = q->left; st.push(q); } } } return vec; }};2. Morris Traversal
/** * Definition for binary tree * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode(int x) : val(x), left(NULL), right(NULL) {} * }; */class Solution {public: vector<int> inorderTraversal(TreeNode *root) { vector<int> vec; TreeNode *cur, *pre; cur = root; while(cur) { if(cur->left == NULL) { vec.push_back(cur->val); cur = cur->right; } else { pre = cur->left; while(pre->right && pre->right != cur) pre = pre->right; if(pre->right == NULL) { pre->right = cur; cur = cur->left; } else { pre->right = NULL; vec.push_back(cur->val); cur = cur->right; } } } return vec; }};
37. Binary Tree Zigzag Level Order Traversal && Binary Tree Inorder Traversal