二叉树遍历

前言

在学习或工作中，总会遇到和算法相关的问题。
而二叉树在算法中是绕不过的一个场景。 这里介绍下二叉树的相关遍历方法。

二叉树遍历

• 前序遍历
  前序遍历首先访问根节点，然后遍历左子树，最后遍历右子树。

class Solution {
public:
  void addTreeNode(vector<int> &treeVector, TreeNode* root) {
        if (root == NULL) {
            return ;
        }
        // 前序遍历，优先查找根节点
        treeVector.push_back(root->val);
        addTreeNode(treeVector, root->left);
        addTreeNode(treeVector, root->right);
    } 
    vector<int> preorderTraversal(TreeNode* root) {
        vector<int> treeVector;
        addTreeNode(treeVector, root);
        return treeVector;
    }    
};

• 中序遍历
  中序遍历是先遍历左子树，然后访问根节点，然后遍历右子树。
  tips: 通常来说，对于二叉搜索树，我们可以通过中序遍历得到一个递增的有序序列

• 后序遍历
  后序遍历是先遍历左子树，然后遍历右子树，最后访问树的根节点。

• 层序遍历
  层序遍历就是逐层遍历树结构。
  广度优先搜索是一种广泛运用在树或图这类数据结构中，遍历或搜索的算法.
  该算法从一个根节点开始，首先访问节点本身。 然后遍历它的相邻节点，其次遍历它的二级邻节点、三级邻节点，以此类推

class Solution {
public:

    void helper(vector<vector<int>> &res, TreeNode* root, int leval) {
            if (root == NULL) {
                return;
            }
            if (res.size() <= leval) {
                vector<int> tmp;
                res.push_back(tmp);
            }
            res[leval].push_back(root->val);
            helper(res, root->left, leval + 1);
            helper(res, root->right, leval + 1);
    }

    vector<vector<int>> levelOrder(TreeNode* root) {
        vector<vector<int>> res;
        helper(res, root, 0);
        return res;
        
    }
};