二叉树的层序遍历与深度遍历

二叉树

今天学习并回顾了二叉树，对其基本算法进行了重写。如有可优化的地方，欢迎指正！代码均在Leetcode上跑过了。

层序遍历(Leetcode102题)

由于用前面写算法都是用C语言写的，像栈、队列每次都得手敲一遍。这里为了简化代码，使用C++进行代码编写。以后也转化为用C++写算法题。
My Coding

class Solution {
public:/*** By passing in a binary tree, return a two-dimensional array to record which nodes are present in each layer** @param root is a pointer to TreeNode type, is the head node of a binary tree** @return a two-dimensional array, with each row corresponding to each layer of the binary tree*/vector<vector<int>> levelOrder(TreeNode* root) {queue<TreeNode*> q;             //创建一个队列vector<vector<int>> vec;        //二维数组,泛型每一行存int型数据if(root == NULL)return vec;     //判断二叉树是否存在vec.push_back(vector<int>());   //预先分配一行int level = 1;                  //到此至少存在一层q.push(root);                   //将root送入队列qmap<TreeNode*,int> m;           //定义一个map,记录每个结点对应的层次m.insert(map<TreeNode*,int>::value_type(root,1));   //map插入数据root,1 表示root在第一层while(!q.empty())               //循环判定队列是否为空,为空则已遍历完{TreeNode *cur = q.front();  //获取队列最前结点q.pop();                    //并将其出队int curLevel = m[cur];      //通过key-value获取其所在层次if(level == curLevel)       //判断level是否等于curLevel,这一步用于判定是否来到下一层{vec[level-1].push_back(cur->val);   //将同一层的结点对应值加入数组中}else    {vec.push_back(vector<int>());       //处于不同层级，新建一行level++;    //更新层级，注意要将当前结点值加入新行数组中vec[level-1].push_back(cur->val);}/* 不用担心cur为空,因为从第一个root开始，只会对不为空的结点进行操作 */if(cur->left != NULL)   //如果左孩子存在，则放入队列并置入哈希表中{m.insert(map<TreeNode*,int>::value_type(cur->left,level + 1));  //左孩子肯定是在下一层q.push(cur->left);}/* 不用担心cur为空,因为从第一个root开始，只会对不为空的结点进行操作 */if(cur->right != NULL)  //如果左孩子存在，则放入队列并置入哈希表中{m.insert(map<TreeNode*,int>::value_type(cur->right,level + 1)); //右孩子肯定是在下一层q.push(cur->right);}}return vec; //返回二维数组。}
};

官方

class Solution {
public:vector<vector<int>> levelOrder(TreeNode* root) {vector <vector <int>> ret;      //创建二维数组if (!root) {                    //判断是否为空,为空则返回return ret;}queue <TreeNode*> q;            //创建队列 qq.push(root);                   //将root加入队列while (!q.empty()) {            //判断二叉树是否遍历完int currentLevelSize = q.size();    //获取当前层级结点个数ret.push_back(vector <int> ());for (int i = 1; i <= currentLevelSize; ++i) {   //循环将数据填入二维数组中auto node = q.front(); q.pop();ret.back().push_back(node->val);if (node->left) q.push(node->left);     //每次将左孩子加入队列（前提不为空）if (node->right) q.push(node->right);   //每次将有孩子加入队列（前提不为空）}}return ret;     返回二维数组}
};

总结: 官方写的更为整洁、简短。值得好好学习。

深度遍历

采用递归算法则相对简单

先序遍历(Leetcode 144题)

递归算法(递归就不分析了)

class Solution {
public:void preorder(TreeNode *root, vector<int> &res) {if (root == nullptr) {return;}res.push_back(root->val);preorder(root->left, res);preorder(root->right, res);}vector<int> preorderTraversal(TreeNode *root) {vector<int> res;preorder(root, res);return res;}
};

非递归算法
注意:压栈一定是先右再左,这样取出来才是先序

class Solution {
public:vector<int> preorderTraversal(TreeNode* root) {vector<int> vec;                //创建一维数组if(root == NULL)return vec;     //如果root为空，则返回stack<TreeNode*> st;            //创建一个栈st.push(root);                  //将root压栈while(!st.empty())              //判断二叉树是否遍历完{   TreeNode* cur = st.top();   //获取栈顶元素st.pop();                   //弹出栈顶元素vec.push_back(cur->val);    //将当前结点值加入数组if(cur->right)              //右孩子不为空则压栈{st.push(cur->right);}if(cur->left)               //左孩子不为空则压栈{st.push(cur->left);}}return vec;     //返回一维数组}
};

中序遍历(Leetcode 94题)

递归算法(递归就不分析了)

class Solution {
public:void preorder(TreeNode *root, vector<int> &res) {if (root == nullptr) {return;}preorder(root->left, res);res.push_back(root->val);preorder(root->right, res);}vector<int> preorderTraversal(TreeNode *root) {vector<int> res;preorder(root, res);return res;}
};

非递归算法

class Solution {
public:vector<int> inorderTraversal(TreeNode* root) {vector<int> vec;    //创建一维数组if(root == NULL)    //如果root为空则返回vec{return vec;}stack<TreeNode*> st;    //创建一个栈while(!st.empty() || root != NULL)  //栈内有值或root不为空时循环{if(root != NULL)    //root不为空，则一直将左孩子压栈{st.push(root);root = root->left;}else                //保存栈顶元素，并将root切换到右孩子{root = st.top();st.pop();vec.push_back(root->val);root = root->right;}}return vec;             //返回一维数组}
};

后序遍历(Leetcode 145题)

递归算法(递归就不分析了)

class Solution {
public:void preorder(TreeNode *root, vector<int> &res) {if (root == nullptr) {return;}preorder(root->left, res);preorder(root->right, res);res.push_back(root->val);}vector<int> preorderTraversal(TreeNode *root) {vector<int> res;preorder(root, res);return res;}
};

非递归算法
采用双栈

class Solution {
public:vector<int> postorderTraversal(TreeNode* root) {vector<int> vec;    //创建一维数组if(root == NULL)    //如果root为空则返回vec{return vec;}stack<TreeNode*> st1;   //栈1stack<TreeNode*> st2;   //栈2st1.push(root);         //root压栈while(!st1.empty())     //第一次遍历完二叉树{root = st1.top();   //弹出栈顶元素st1.pop();st2.push(root);     //将该结点压入栈2if(root->left)      //如果有左孩子，则压栈1{st1.push(root->left);}if(root->right)     //如果有右孩子，则压栈2{   st1.push(root->right);}}/* 此时栈2的压栈顺序为中右左，取出则为左右中，为后序 */while(!st2.empty())     //循环将栈2中的数据弹出保存到一维数组中{root = st2.top();st2.pop();vec.push_back(root->val);}return vec;             //返回一维数组}
};