首页 > 代码库 > 算法 二叉树的各种遍历
算法 二叉树的各种遍历
二叉树的遍历方式基本就是前序遍历，中序遍历，后序遍历和层次遍历。从代码的角度来说，前三种最简单的就是用递归了，代码会非常简洁。但是递归有一个缺陷，就是当二叉树的节点非常多的时候，层次深的递归会不停的进行程序的压栈和出栈操作，效率比较低。这里就不写递归算法了，只写四种遍历的非递归算法。
先定义二叉树的节点如下：
/**
* Definition for binary tree
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
前序中序后序三种非递归算法都要借助于栈来实现，层次遍历要借助于队列实现。
前序遍历
Given a binary tree, return the preorder traversal of its nodes‘ values.
For example:
Given binary tree {1,#,2,3},
1
2
/
3
return [1,2,3].
前序遍历在四种之中最简单，就是先把根节点进栈，然后一直出栈并不断把当前节点的右儿子和左儿子依次进栈。注意，必须先右儿子后左儿子。代码如下，
public List<Integer> preorderTraversal(TreeNode root) {
List<Integer> list=new ArrayList<Integer>();
if(root==null)
{
return list;
}
Stack<TreeNode> stack=new Stack<TreeNode>();
stack.push(root);
while(!stack.empty())
{
TreeNode node=stack.pop();
list.add(node.val);
if(node.right!=null)
{
stack.push(node.right);
}
if(node.left!=null)
{
stack.push(node.left);
}
}
return list;
}
中序遍历
Given a binary tree, return the inorder traversal of its nodes‘ values.
For example:
Given binary tree {1,#,2,3},
1
2
/
3
return [1,3,2].
先将根节点进栈，然后不停的找到当前节点的左儿子节点，知道没有左儿子，然后当前节点出栈，访问，右儿子进栈。
public List<Integer> inorderTraversal(TreeNode root) {
List<Integer> list=new ArrayList<Integer>();
if(root==null)
{
return list;
}
Stack<TreeNode> stack=new Stack<TreeNode>();
stack.push(root);
while(!stack.empty())
{
TreeNode node=null;
while((node=stack.peek())!=null)
{
stack.push(node.left);
}
stack.pop();
if(!stack.empty()){
node=stack.pop();
list.add(node.val);
stack.push(node.right);
}
}
return list;
}
后序遍历
Given a binary tree, return the postorder traversal of its nodes‘ values.
For example:
Given binary tree {1,#,2,3},
1
2
/
3
return [3,2,1].
public List<Integer> postorderTraversal(TreeNode root) {
List<Integer> list=new ArrayList<Integer>();
if(root==null)
{
return list;
}
TreeNode pre=null;
Stack<TreeNode> stack=new Stack<TreeNode>();
stack.push(root);
while(!stack.empty())
{
TreeNode node=stack.peek();
if((node.left==null&&node.right==null)||(pre!=null&&(pre==node.left||pre==node.right)))
{
list.add(node.val);
pre=node;
stack.pop();
}
else
{
if(node.right!=null)
{
stack.push(node.right);
}
if(node.left!=null)
{
stack.push(node.left);
}
}
}
return list;
}
层次遍历
Given a binary tree, return the level order traversal of its nodes‘ values. (ie, from left to right, level by level).
For example:
Given binary tree {3,9,20,#,#,15,7},
3
/ 9 20
/ 15 7
return its level order traversal as:
[ [3], [9,20], [15,7] ]层次遍历需要借助队列结构，队列是想FIFO的结构，和层次遍历的书序正好一致。
本题的描述比一般的层次遍历更复杂一些，不但要层次遍历，还要每个层单独的一个list。这里定义一个变量count,初始值为1，表示当前层次的节点数。这样在循环的时候，只要遍历了count个节点就表示当前层次的节点都访问完了。
public List<List<Integer>> levelOrder(TreeNode root) {
List<List<Integer>> result=new ArrayList<List<Integer>>();
LinkedList<TreeNode> queue=new LinkedList<TreeNode>();
if(root==null)
{
return result;
}
int count=0;
queue.add(root);
count=1;
while(queue.size()!=0)
{
int temp=0;
List<Integer> list=new ArrayList<Integer>();
for(int i=0;i<count;i++)
{
TreeNode node=queue.poll();
if(node!=null)
{
list.add(node.val);
if(node.left!=null)
{
queue.add(node.left);
temp++;
}
if(node.right!=null)
{
queue.add(node.right);
temp++;
}
}
}
result.add(list);
count=temp;
}
return result;
}
以上所有的代码都在LeetCode测试并通过。
算法 二叉树的各种遍历