前序遍历：根节点 左子树 右子树
中序遍历：左子树 根节点 右子树
后序遍历：左子树 右子树 根节点
层序遍历：每一层从左到右访问每一个节点

• 前序遍历（递归）

vector<int> preorderTraversal(TreeNode* root){
    vector<int> ret;
    dfsPreOrder(root,ret);
    return ret;
}
void dfsPreOrder(TreeNode* root,vector<int> &ret){
    if(root==NULL) return;
    ret.push_back(root->val);//存储根节点
    if(root->left!=NULL) dfsPreOrder(root->left,ret);//访问左子树
    if(root->right!=NULL) dfsPreOrder(root->right,ret);//访问右子树
}

循环实现：

vector<int> preorderTraversal(TreeNode* root) {
    vector<int> ret;
    if (root==NULL) return ret;
    stack<TreeNode*> st;
    st.push(root);
    while(!st.empty())
    {
        TreeNode* tp = st.top();//取出栈顶元素
        st.pop();
        ret.push_back(tp->val);//先访问根节点
        if(tp->right!=NULL) st.push(tp->right);//由于栈时先进后出，考虑到访问顺序，先将右子树压栈
        if(tp->left!=NULL) st.push(tp->left);//将左子树压栈
    }
    return ret;
}
Python 实现：
def preOrder(root):
    if not root:
        return
    s = []
    res = []
    s.append(root)
    while s:
        node = s.pop()
        res.append(node.val)
        if node.right:
            s.append(node.right)
        if node.left:
            s.append(node.left) 
    return res
            

• 中序遍历（递归）

vector<int> inorderTraversal(TreeNode* root) {
    vector<int> ret;
    inorder(root,ret);
    return ret;
}
void inorder(TreeNode* p,vector<int>& ret)
{
    if(p==NULL) return;
    inorder(p->left,ret);//访问左子树
    ret.push_back(p->val);//访问根节点
    inorder(p->right,ret);//访问右子树
}

循环实现

vector<int> inorderTraversal(TreeNode* root) {
    vector<int> ret;
    TreeNode* p = root;
    stack<TreeNode*> st;
    while(!st.empty()||p!=NULL){
        if(p){//p非空，代表还有左子树，继续
            st.push(p);
            p=p->left;
        }
        else{//如果为空，代表左子树已经走到尽头了
            p = st.top();
            st.pop();
            ret.push_back(p->val);//访问栈顶元素
            if(p->right) {
                st.push(p->right);//如果存在右子树，将右子树入栈
                p = p->right->left;//p始终为下一个待访问的节点
            }
            else p=NULL;
        }
    }
    return ret;
}
Python 实现：
def inorder(root):
    if not root:
        return
    s = []
    res = []
    node = root
    while node or s:
        if node:
            s.append(node)
            node = node.left
        else:
            node = s.pop()
            res.append(node.val)
            node = node.right
    return res

• 后序遍历（递归）

vector<int> inorderTraversal(TreeNode* root) {
    vector<int> ret;
    inorder(root,ret);
    return ret;
 }
void inorder(TreeNode* p,vector<int>& ret)
{
    if(p==NULL) return;
    inorder(p->left,ret);//访问左子树
    inorder(p->right,ret);//访问右子树
    ret.push_back(p->val);//访问根节点
}

循环实现

vector<int> postorderTraversal(TreeNode* root) {
    vector<int> ret;
    TreeNode* p = root;
    stack<TreeNode*> st;
    TreeNode* r = NULL;
    while(p||!st.empty())
    {
        if(p)
        {
            st.push(p);
            p = p -> left;
        }
        else
        {
            p = st.top();
            if(p->right&&p->right!=r)
            {
                p = p->right;
                st.push(p);
                p = p->left;
            }
            else 
            {
                p = st.top();
                st.pop();
                ret.push_back(p->val);
                r= p;
                p = NULL;
            }
        }
    }
    return ret;
}
python 实现：
def afterOrder(root):
    if not root:
        return
    s1 = []
    s2 = []
    res = []
    s1.append(root)
    while s1:
        node = s1.pop()
        s2.append(node)
        if node.left:
            s1.append(node.left)
        if node.right:
            s1.append(node.right)
    while s2:
        top = s2.pop()
        res.append(top.val)
    return res

根据前序遍历和中序遍历构造二叉树：

class TreeNode(object):
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None

def buildTree(preorder, inorder):
    """
    根据前序遍历和中序遍历构造二叉树
    """
    if inorder:
        ind = inorder.index(preorder.pop(0))
        root = TreeNode(inorder[ind])
        root.left = buildTree(preorder, inorder[0:ind])
        root.right = buildTree(preorder, inorder[ind+1:])
        return root

根据后序遍历和中序遍历构造二叉树

def buildTree1(inorder, postorder ):
    if inorder:
        ind = inorder.index(postorder.pop())
        root = TreeNode(inorder[ind])
        root.right = buildTree(inorder[ind+1:], postorder)
        root.left = buildTree(inorder[:ind], postorder)
        return root

广度优先 队列实现，可以使用 list

def level_queue(root):
    if root is None:
        return
    my_queue = []
    node = root
    my_queue.append(node)
    while my_queue:
        node = my_queue.pop(0)
        print node.val
        if not node.left:
            my_queue.append(node.left)
        if not node.right:
            my_queue.append(node.right)

深度优先

def depth_tree(root):
    if root is not None:
        print root.val
        if not root.left:
            return depth_tree(root.left)
        if not root.right:
            return depth_tree(root.right)