DFS

深度优先搜索学习笔记。

/**

• Definition for a binary tree node.
• struct TreeNode {

• int val;
  

• TreeNode *left;
  

• TreeNode *right;
  

• TreeNode(int x) : val(x), left(NULL), right(NULL) {}
  

• }; / class Solution { public: // 在分层遍历的基础上，加入一个flag 表示奇数层和偶数层 vector<vector> printFromTopToBottom(TreeNode root) { vector<vector> res; if(! root) return res; vector level; queue<TreeNode *> q; q.push(root); q.push(nullptr); bool st =false; while(q.size()) { auto t =q.front(); q.pop(); if(t) { level.push_back(t-> val); if(t-> left) q.push(t->left); if(t-> right) q.push(t->right); } else { if(level.empty()) break; if(st) reverse(level.begin(), level.end()); st =! st; res.push_back(level); level.clear(); q.push(nullptr); } } return res; } };