前序遍历：根节点 左子树 右子树
中序遍历：左子树 根节点 右子树
后序遍历：左子树 右子树 根节点
层序遍历：每一层从左到右访问每一个节点
- 前序遍历（递归）
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)
