训练题：序列化二叉树

题目：https://leetcode-cn.com/problems/xu-lie-hua-er-cha-shu-lcof/

  2. // 宽度优先遍历
  3. string serialize( TreeNode* root )
  4. {
  5.     if( !root ) { return ""; }
  7.     queue<TreeNode*> q;
  8.     TreeNode* tmpNode = nullptr;
  9.     string ret;
  11.     for( q.push( root ); !q.empty(); q.pop() )
  12.     {
  13.         tmpNode = q.front();
  14.         if( tmpNode )
  15.         {
  16.             ret.append( to_string( tmpNode->val ) );
  17.             q.push( tmpNode->left );
  18.             q.push( tmpNode->right );
  19.         }
  20.         ret.append( "," );
  21.     }
  23.     return ret;
  24. }
  26. // Decodes your encoded data to tree.
  27. TreeNode* deserialize( string data )
  28. {
  29.     if( data.empty() ) { return nullptr; }
  31.     const auto size = data.size();
  32.     queue<TreeNode*> q;
  33.     stringstream ss;
  34.     TreeNode* tmpNewNode = nullptr;
  35.     TreeNode* tmpNode    = nullptr;
  36.     TreeNode* root       = nullptr;
  37.     bool start      = true;
  38.     bool tmpSuccess = false;
  39.     bool tmpLeft    = true;
  40.     int tmpVal;
  42.     for( int startIdx = 0, endIdx = startIdx; endIdx != size; ++endIdx )
  43.     {
  44.         if( data[endIdx] == ',' )
  45.         {
  46.             tmpSuccess = parseVal( data, ss, startIdx, endIdx, tmpVal );
  47.             if( tmpSuccess ) { tmpNewNode = new TreeNode( tmpVal ); }
  48.             else { tmpNewNode = nullptr; }
  50.             if( start )
  51.             {
  52.                 if( !tmpNewNode ) { return nullptr; }
  53.                 root = tmpNewNode;
  54.                 q.push( tmpNewNode );
  55.                 tmpLeft = true;
  56.                 start = false;
  57.             }
  58.             else
  59.             {
  60.                 tmpNode = q.front();
  61.                 if( tmpLeft ) { tmpNode->left = tmpNewNode; }
  62.                 else
  63.                 {
  64.                     tmpNode->right = tmpNewNode;
  65.                     q.pop();
  66.                 }
  67.                 if( tmpNewNode ) { q.push( tmpNewNode ); }
  68.                 tmpLeft = !tmpLeft;
  69.             }
  71.             startIdx = endIdx + 1;
  72.         }
  73.     }
  74.     return root;
  75. }
  77. bool parseVal( const string &data, stringstream &ss, const int &start, const int &end, int &val )
  78. {
  79.     if( end <= start ) { return false; }
  80.     ss << data.substr( start, end - start );
  81.     ss >> val;
  82.     ss.clear();
  83.     return true;
  84. }

训练题：二叉树后续遍历序列

题目：https://leetcode-cn.com/problems/er-cha-sou-suo-shu-de-hou-xu-bian-li-xu-lie-lcof/

方法一：递归（模拟法）

  • 时间复杂度：O（n2）
  • 空间复杂度：O（n）
  2. bool verifyPostorder( vector<int> &postorder )
  3. {
  4.     if( postorder.size() > 1000 ) { return false; }
  6.     return traverse( postorder, 0, static_cast<short>( postorder.size() - 1 ) );
  7. }
  9. bool traverse( vector<int> &postorder, short start, short end )
  10. {
  11.     if( end <= start ) { return true; }
  13.     // 左子树区间：[start, leftEnd)
  14.     short leftEnd = start;
  15.     for( ; leftEnd < end && postorder[leftEnd] < postorder[end]; ++leftEnd );
  17.     // 存在左子树区间，则递归遍历。
  18.     if(leftEnd != start && !traverse( postorder, start, leftEnd-1 )) return false;
  20.     if(leftEnd != end){
  21.         // 右子树区间：[leftEnd, rightEnd)
  22.         short rightEnd = leftEnd;
  23.         for( ; rightEnd < end && postorder[rightEnd] > postorder[end]; ++rightEnd);
  25.         // 如果是二叉搜索树，则右子树区间应该是[leftEnd, end)，即rightEnd = end。
  26.         if(rightEnd != end) return false;
  28.         // 递归遍历右子树区间
  29.         if( !traverse( postorder, leftEnd, rightEnd-1 ) ) { return false; }
  30.     }
  32.     return true;
  33. }

方法二：栈

  • 时间复杂度：O（n）
  • 空间复杂度：O（n） ```cpp

bool verifyPostorder( vector &postorder ) { if( postorder.size() > 1000 ) { return false; }

  1. stack<int> stk;
  2. int root = INT_MAX;
  3. for(auto it = postorder.rbegin(); it != postorder.rend(); ++it){
  4.     if(root < *it) return false;
  5.     for(; !stk.empty() && *it < stk.top(); stk.pop()) root = stk.top();
  6.     stk.push(*it);
  7. }
  8. return true;

}

  1. <a name="JxWmC"></a>
  2. # 训练题：二叉树查找路径
  3. 题目：[http://t.cn/A6qUHzz3](http://t.cn/A6qUHzz3)
  4. <a name="M0UNJ"></a>
  5. ## 方法：递归
  6. ```cpp
  8. vector<vector<int>> pathSum(TreeNode* root, int target) {
  9.     if(!root) return {};
  11.     vector<vector<int>> data;
  12.     vector<int> path;
  13.     int sum = target;
  15.     traverse(root, data, path, sum);
  17.     return data;
  18. }
  20. void traverse(TreeNode* root,vector<vector<int>> &data, vector<int>& path, int &sum){
  22.     if(!root) return;
  24.     path.push_back(root->val);
  25.     sum -= root->val;
  27.     if(!root->left && !root->right && !sum) data.push_back(path);
  28.     else
  29.     {
  30.         traverse(root->left, data, path, sum);
  31.         traverse(root->right, data, path, sum);
  32.     }
  34.     sum += root->val;
  35.     path.pop_back();
  36. }

训练题：二叉搜索树转链表

题目：http://t.cn/A6q5lHBc

递归方法一

  2. Node* treeToDoublyList(Node* root) {
  3.     if(!root) return root;
  5.     Node head, *tail = &head;
  7.     // 中序遍历root，转化成双向链表，并返回链表表尾
  8.     tail = traverse(root, tail);
  10.     // 表尾与表头接上。
  11.     tail->right = head.right;
  12.     head.right->left = tail;
  14.     return head.right;
  15. }
  17. Node* traverse(Node* root, Node* tail){
  18.     if(!root) return tail;
  20.     tail = traverse(root->left, tail);
  22.     tail->right = root;
  23.     root->left = tail;
  24.     tail = root;
  26.     return traverse(root->right, tail);
  27. }

递归方法二

  2. class Solution {
  3. public:
  4.     Node* treeToDoublyList(Node* root) {
  5.         if(!root) return root;
  7.         traverse(root);
  8.         head->left = tail;
  9.         tail->right = head;
  10.         return head;
  11.     }
  12. private:
  13.     Node* head, *tail;
  14.     void traverse(Node* root){
  15.         if(!root) return;
  17.         traverse(root->left);
  19.         if(!head) head = tail = root;
  20.         else tail->right = root;
  21.         root->left = tail;
  22.         tail = root;
  23.         traverse(root->right);
  24.     }
  25. };

训练题：判断二叉树平衡

题目：http://t.cn/A6qYF1Mg

方法一：递归一

  2. bool isBalanced(TreeNode* root) {
  3.     if(!root) return true;
  4.     return abs(depth(root->left) - depth(root->right)) <= 1 && isBalanced(root->left) && isBalanced(root->right);
  5. }
  7. // 递归求root的深度
  8. int depth(TreeNode* root){
  9.     if(!root) return 0;
  10.     return max(depth(root->left), depth(root->right)) + 1;
  11. }

方法二：递归二

  2. bool isBalanced(TreeNode* root) {
  3.     return traverse(root) != -1;
  4. }
  6. int traverse(TreeNode* root)
  7. {
  8.     if(!root) return 0;
  10.     int left = traverse(root->left);
  11.     if(left == -1) return -1;
  13.     int right = traverse(root->right);
  14.     if(right == -1) return -1;
  16.     return abs(left - right) < 2 ? max(left, right) + 1 : -1;
  17. }

训练题：最近公共祖先（LCA）

场景一：二叉搜索树

递归法

  2. // 递归方法一：实测结果，这个更快一点
  3. TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
  4.     if(!root || root == p || root == q) return root;
  6.     if((root->val - p->val)*(root->val - q->val) < 0) return root;
  7.     if(root->val > p->val && root->val > q->val) return lowestCommonAncestor(root->left, p, q);
  8.     else return lowestCommonAncestor(root->right, p, q); 
  9. }
  11. // 递归方法二：
  12. TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
  14.     if(!root || root == p || root == q) return root;
  16.     if(max(p->val, q->val) < root->val) return lowestCommonAncestor(root->left, p, q);
  17.     if(min(p->val, q->val) > root->val) return lowestCommonAncestor(root->right, p, q); 
  19.     return root;
  20. }

迭代法

  2. TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
  3.     while(true) 
  4.     {
  5.         if( min(p->val, q->val) > root->val ) root = root->right;
  6.         else if( max(p->val, q->val) < root->val ) root = root->left;
  7.         else break;
  8.     }
  9.     return root;
  10. }

场景二：普通二叉树

题目：http://t.cn/A65Tm8ou

方法一：递归

  2. // 由于递归的深度优先特性（从下往上遍历），找到的一个公共祖先其实就是深度最大的祖先，即最近公共祖先。
  4. // root为遍历的当前根节点，p、q为其下的节点。
  5. TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
  6.     // 优先遍历到了p或者q节点、或者到叶节点都没有遍历到。
  7.     if(!root || root == p || root == q) return root;
  9.     // 分别遍历了一遍左右子树，分别得到了left/right节点
  10.     TreeNode* left  = lowestCommonAncestor(root->left, p, q);
  11.     TreeNode* right = lowestCommonAncestor(root->right, p, q);
  13.     // 如果left为空，而right不为空，则表示p是q的子节点，或者反之，只有这样才会导致遍历到p或者q就停止了。
  14.     // right为空，left不为空同理。
  15.     //
  16.     // 如果left不为空且right不为空，则表示p、q分别在左右子树中，因此公共祖先应该是root。
  17.     return !left ? right : (!right ? left : root);
  18. }

方法二：哈希表

用哈希表记录每个节点的父节点。问题就变成了查找两个链表的第一个公共节点。
见：https://www.yuque.com/tvvhealth/cs/pn55xq

  2. TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
  4.     map<TreeNode*, TreeNode*> info;
  5.     recordParent(root, info);
  7.     TreeNode* nodep = p, *nodeq = q;
  8.     while(nodep != nodeq){
  9.         nodep = nodep == root ? q : info[nodep];
  10.         nodeq = nodeq == root ? p : info[nodeq];
  11.     }
  13.     return nodep;
  14. }
  16. void recordParent(TreeNode* root, map<TreeNode*, TreeNode*>& info){
  17.     if(!root) return;
  18.     if(root->left) info[root->left] = root;
  19.     if(root->right) info[root->right] = root;
  20.     recordParent(root->left, info);
  21.     recordParent(root->right, info);
  22. }

训练题：二叉搜索树K大数

题目：http://t.cn/A6qjYlXa

方法一：递归

  2. int kthLargest(TreeNode* root, int k) {
  4.     int val;
  5.     traverse(root, val, k);
  6.     return val;
  8. }
  10. void traverse(TreeNode* root, int&val, int &k){
  11.     if(!k || !root) return;
  13.     traverse(root->right, val, k);
  14.     if(!(--k)){
  15.         val = root->val;
  16.         return;
  17.     }
  18.     traverse(root->left, val, k);
  19. }

方法二：迭代

  2. int kthLargest(TreeNode* root, int k) {
  4.     stack<TreeNode*> stk;
  6.     stk.push(root);
  8.     while(!stk.empty()){
  10.         root = stk.top();
  11.         stk.pop();
  13.         if(!root->right && !--k){
  14.             return root->val;
  15.         }
  17.         if(root->left) stk.push(root->left);
  18.         stk.push(root);
  19.         if(root->right) stk.push(root->right);
  20.     }
  22.     return -1;
  23. }

训练题：二叉树深度

题目：http://t.cn/A6qjTSIv

方法一：递归

  2. int maxDepth(TreeNode* root) {
  3.     if(!root) return 0;
  4.     return max(maxDepth(root->left), maxDepth(root->right)) + 1;
  5. }

方法二：迭代

广度优先算法。

  2. int maxDepth(TreeNode* root) {
  4.     int depth = 0;
  5.     queue<TreeNode*> q1, q2;
  6.     TreeNode* node;
  8.     if(root) q1.push(root);
  10.     while(!q1.empty() || !q2.empty()){
  11.         if(!q1.empty()){
  12.             ++depth;
  13.             while(!q1.empty()){
  14.                 node = q1.front();
  15.                 q1.pop();
  16.                 if(node->left) q2.push(node->left);
  17.                 if(node->right) q2.push(node->right);
  18.             }
  19.         }
  20.         if(!q2.empty()){
  21.             ++depth;
  22.             while(!q2.empty()){
  23.                 node = q2.front();
  24.                 q2.pop();
  25.                 if(node->left) q1.push(node->left);
  26.                 if(node->right) q1.push(node->right);
  27.             }
  28.         }
  29.     }
  31.     return depth;
  32. }

训练题：重建二叉树

题目：http://t.cn/A6z20HLo

方法一：递归

  • 时间复杂度：O(n)
  • 空间复杂度：O(n) ```cpp

TreeNode* buildTree( vector &preorder, vector &inorder ) { if( preorder.empty() || preorder.size() != inorder.size() ) { return nullptr; }

  1. const auto size_pre = preorder.size();
  2. const auto size_in = inorder.size();
  3. map<int, int> inMap;
  5. for( int i = 0; i < size_in; ++i ) { inMap[inorder[i]] = i; }
  7. return _build( preorder, inorder, inMap, 0, size_pre - 1, 0, size_in - 1 );

}

TreeNode* _build( const vector &preorder, const vector &inorder, map &inMap, const int &preStart, const int &preEnd, const int &inStart, const int &inEnd ) { if( preStart > preEnd ) { return nullptr; }

  1. TreeNode* root = new TreeNode( preorder[preStart] );
  3. if( preStart == preEnd ) { return root; }
  5. // 当前根节点在中序遍历中的索引。
  6. int rootIdx_in = inMap[preorder[preStart]];
  8. root->left = _build( preorder, inorder, inMap, preStart + 1, preStart + rootIdx_in - inStart, inStart, rootIdx_in - 1 );
  9. root->right = _build( preorder, inorder, inMap, preStart + rootIdx_in - inStart + 1, preEnd, rootIdx_in + 1, inEnd );
  11. return root;

}

  1. <a name="QQ8hK"></a>
  2. ## 方法二：迭代（待完成）
  3. ```cpp

训练题：树的子结构

题目：http://t.cn/A6GgETFz

方法一：双递归

递归一：遍历目标子树
递归二：在递归一的每个子过程中，再递归检测当前递归节点为根节点的目标子树。

  • 时间复杂度：O(AB)
  • 空间复杂度：O(A) ```cpp

// 递归1 bool isSubStructure( TreeNode A, TreeNode B ) { if( !A || !B ) { return false; } return fuck( A, B ) || isSubStructure( A->left, B ) || isSubStructure( A->right, B ); }

// 递归2 bool fuck( TreeNode A, TreeNode B ) { return !B || A && A->val == B->val && fuck( A->left, B->left ) && fuck( A->right, B->right ); }

  1. <a name="d3WYD"></a>
  2. # 训练题：树的镜像
  3. 题目：[http://t.cn/A6GgnP1E](http://t.cn/A6GgnP1E)
  4. <a name="e5KM1"></a>
  5. ## 方法一：递归
  7. - 时间复杂度：O(n)
  8. - 空间复杂度：O(n)
  9. ```cpp
  11. TreeNode* mirrorTree(TreeNode* root) {
  12.     if(!root) return root;
  14.     TreeNode* tmpNode = nullptr;
  15.     tmpNode = root->left;
  16.     root->left = mirrorTree(root->right);
  17.     root->right = mirrorTree(tmpNode);
  19.     return root;
  20. }

方法二：迭代（辅助栈/队列）

  2. TreeNode* mirrorTree(TreeNode* root) {
  3.     if(!root) return root;
  5.     queue<TreeNode*> q;        // 可以用栈/队列
  6.     q.push(root);
  8.     for(TreeNode* node, *tmpNode; !q.empty();){
  9.         node = q.front();
  10.         q.pop()
  11.         tmpNode = node->left;
  12.         node->left = node->right;
  13.         node->right = tmpNode;
  14.         if(node->left)  q.push(node->left);
  15.         if(node->right) q.push(node->right);
  16.     }
  18.     return root;
  19. }

训练题：对称二叉树

题目：http://t.cn/A6GgnWmH

方法一：递归

  2. bool isSymmetric(TreeNode* root) {
  3.     if(!root) return true;
  4.     return fuck(root->left, root->right);
  5. }
  7. bool fuck(TreeNode* left, TreeNode* right){
  8.     if(!left && !right) return true;
  9.     if(!left || !right || left->val != right->val) return false;
  10.     return fuck(left->left, right->right) && fuck(left->right, right->left);
  11. }

方法二：迭代

既然可以递归，那就可以考虑迭代。
如果是对称的，则中-左-右和中-右-左遍历的每一步都是对称的。可以用队列或者栈。

  2. bool isSymmetric(TreeNode* root) {
  3.     if(!root || !root->left && !root->right) return true;
  4.     if(!root->left || !root->left) return false;
  6.     queue<TreeNode*> q1, q2;
  7.     q1.push(root);
  8.     q2.push(root);
  10.     for(TreeNode* tmpNode1, *tmpNode2; !q1.empty() && !q2.empty();) {
  11.         tmpNode1 = q1.front();
  12.         tmpNode2 = q2.front();
  13.         q1.pop();
  14.         q2.pop();
  15.         if(!tmpNode1 && !tmpNode2){}
  16.         else if(tmpNode1 && tmpNode2 && tmpNode1->val == tmpNode2->val){}
  17.         else return false;
  19.         if(tmpNode1){
  20.             q1.push(tmpNode1->left);
  21.             q1.push(tmpNode1->right);
  22.             q2.push(tmpNode2->right);
  23.             q2.push(tmpNode2->left);
  24.         }
  25.     }
  27.     return true;
  28. }

方法三：迭代（改进）

可以将两个队列合并，将两个遍历的过程每一步都是先后放即可。

  2. bool isSymmetric(TreeNode* root) {
  3.     if(!root || !root->left && !root->right) return true;
  4.     if(!root->left || !root->left) return false;
  6.     queue<TreeNode*> q;
  7.     q.push(root);
  8.     q.push(root);
  10.     for(TreeNode* tmpNode1, *tmpNode2; !q.empty();) {
  11.         tmpNode1 = q.front();
  12.         q.pop();
  13.         tmpNode2 = q.front();
  14.         q.pop();
  15.         if(!tmpNode1 && !tmpNode2){}
  16.         else if(tmpNode1 && tmpNode2 && tmpNode1->val == tmpNode2->val){}
  17.         else return false;
  19.         if(tmpNode1){
  20.             q.push(tmpNode1->left);
  21.             q.push(tmpNode2->right);
  22.             q.push(tmpNode1->right);
  23.             q.push(tmpNode2->left);
  24.         }
  25.     }
  26.     return true;
  27. }

训练题：二叉树遍历

场景一：递归遍历（前、中、后）

题目：http://t.cn/A6VhuQIl

  2. /**
  3.  * struct TreeNode {
  4.  *    int val;
  5.  *    struct TreeNode *left;
  6.  *    struct TreeNode *right;
  7.  * };
  8.  */
  10. // 前序遍历
  11. void preOrder( TreeNode* root )
  12. {
  13.     if( !root ) { return; }
  14.     printf("%d", root->val);
  15.     preOrder( root->left, container );
  16.     preOrder( root->right, container );
  17. }
  19. // 中序遍历
  20. void midOrder( TreeNode* root, vector<int> &container )
  21. {
  22.     if( !root ) { return; }
  23.     midOrder( root->left, container );
  24.     printf("%d", root->val);
  25.     midOrder( root->right, container );
  26. }
  28. // 后序遍历
  29. void postOrder( TreeNode* root, vector<int> &container )
  30. {
  31.     if( !root ) { return; }
  32.     postOrder( root->left, container );
  33.     postOrder( root->right, container );
  34.     printf("%d", root->val);
  35. }

场景二：层序遍历

自顶向下

题目：http://t.cn/A6A1oc4c
用队列结构。

  2. vector<vector<int>> levelOrder(TreeNode* root) {
  3.     vector<vector<int>> results{};
  5.     if( !root ) { return results; }
  7.     // 用了两个队列交替进行，避免了记录数的深度
  8.     // 每个队列的节点在同一深度，每次交替深度就会+1
  9.     queue<TreeNode*> q1, q2;
  10.     q1.push( root );
  12.     TreeNode* tmpNode = nullptr;
  14.     auto shit = [&]( queue<TreeNode*> &q_out, queue<TreeNode*> &q_in )
  15.     {
  16.         if( !q_out.empty() ) results.push_back( {} );
  17.         auto &vec = results.back();
  19.         while( !q_out.empty() )
  20.         {
  21.             tmpNode = q_out.front();
  22.             q_out.pop();
  23.             vec.push_back( tmpNode->val );
  25.             if( tmpNode->left ) { q_in.push( tmpNode->left ); }
  26.             if( tmpNode->right )  { q_in.push( tmpNode->right ); }
  27.         }
  28.     };
  30.     while( !q1.empty() || !q2.empty() )
  31.     {
  32.         shit( q1, q2 );
  33.         shit( q2, q1 );
  34.     }
  35.     return results;
  36. }

自底向上

题目：http://t.cn/A6LtHZ0o

  • 思路一
    • 将上面（自顶向下）的结果逆序。
  • 思路二
    • 相对更高效，用list结构代替vector结构，在list头部插入遍历的当前层的结果即可。vector在头部插入的效率很低。不过本地返回类型限制了vector。 ```cpp

vector> levelOrderBottom(TreeNode* root) { vector> results{};

  1. if( !root ) { return results; }
  3. queue<pair<TreeNode*, int>> q;
  4. q.push( { root, 0 } );
  6. TreeNode* tmpNode = nullptr;
  7. int tmpDepth = -1;
  9. while( !q.empty() )
  10. {
  11.     auto data = q.front();
  12.     tmpNode = data.first;
  13.     tmpDepth = data.second;
  15.     q.pop();
  17.     if( tmpDepth == results.size() )results.push_back( {} );
  18.     results[tmpDepth].push_back( tmpNode->val );
  20.     if( tmpNode->left ) q.push( { tmpNode->left, tmpDepth + 1 } );
  21.     if( tmpNode->right )  q.push( { tmpNode->right, tmpDepth + 1 } );
  22. }
  24. reverse(results.begin(), results.end());
  25. return results;

}

  1. <a name="rgOWB"></a>
  2. ## 场景三：之字形遍历
  3. 题目：[http://t.cn/A6VhF78F](http://t.cn/A6VhF78F)
  4. <a name="FlJ11"></a>
  5. ### 方法一
  6. 按场景二层序遍历，然后对偶数位置的vector进行逆序。
  7. ```cpp
  9. vector<vector<int> > zigzagLevelOrder( TreeNode* root )
  10. {
  11.     vector<vector<int>> results{};
  13.     if( !root ) { return results; }
  15.     // 用了两个队列交替进行，避免了记录数的深度
  16.     // 每个队列的节点在同一深度，每次交替深度就会+1
  17.     queue<TreeNode*> q1, q2;
  18.     q1.push( root );
  20.     TreeNode* tmpNode = nullptr;
  22.     auto shit = [&]( queue<TreeNode*> &q_out, queue<TreeNode*> &q_in )
  23.     {
  24.         if( !q_out.empty() ) results.push_back( {} );
  25.         auto &vec = results.back();
  27.         while( !q_out.empty() )
  28.         {
  29.             tmpNode = q_out.front();
  30.             q_out.pop();
  31.             vec.push_back( tmpNode->val );
  33.             if( tmpNode->left ) { q_in.push( tmpNode->left ); }
  34.             if( tmpNode->right )  { q_in.push( tmpNode->right ); }
  35.         }
  36.     };
  38.     while( !q1.empty() || !q2.empty() )
  39.     {
  40.         shit( q1, q2 );
  41.         shit( q2, q1 );
  42.     }
  44.     for( int i = 0; i < results.size(); i++ )
  45.     {
  46.         if( i & 0x1 ) { reverse( results[i].begin(), results[i].end() ); }
  47.     }
  49.     return results;
  50. }

方法二

类似层序遍历用两个queue，这里用两个stack代替。

  2. vector<vector<int> > zigzagLevelOrder( TreeNode* root )
  3. {
  4.     vector<vector<int>> results{};
  6.     if( !root ) { return results; }
  8.     stack<TreeNode*> q1, q2;
  9.     q1.push( root );
  11.     TreeNode* tmpNode = nullptr;
  13.     auto shit = [&]( stack<TreeNode*> &q_out, stack<TreeNode*> &q_in, bool flag )
  14.     {
  15.         if( !q_out.empty() ) results.push_back( {} );
  16.         auto &vec = results.back();
  18.         while( !q_out.empty() )
  19.         {
  20.             tmpNode = q_out.top();
  21.             q_out.pop();
  22.             vec.push_back( tmpNode->val );
  24.             if( flag )
  25.             {
  26.                 if( tmpNode->right )  { q_in.push( tmpNode->right ); }
  27.                 if( tmpNode->left ) { q_in.push( tmpNode->left ); }
  28.                 continue;
  29.             }
  30.             if( tmpNode->left ) { q_in.push( tmpNode->left ); }
  31.             if( tmpNode->right )  { q_in.push( tmpNode->right ); }
  32.         }
  33.     };
  35.     while( !q1.empty() || !q2.empty() )
  36.     {
  37.         shit( q1, q2, false );
  38.         shit( q2, q1, true );
  39.     }
  41.     return results;
  42. }

场景四：N叉树的遍历

原理和二叉树类似，不过是对子节点访问有不同。