首页 > 代码库 > 算法 二叉树的各种遍历

算法 二叉树的各种遍历

二叉树的遍历方式基本就是前序遍历,中序遍历,后序遍历和层次遍历。从代码的角度来说,前三种最简单的就是用递归了,代码会非常简洁。但是递归有一个缺陷,就是当二叉树的节点非常多的时候,层次深的递归会不停的进行程序的压栈和出栈操作,效率比较低。这里就不写递归算法了,只写四种遍历的非递归算法。

先定义二叉树的节点如下:

/**
 * 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测试并通过。

算法 二叉树的各种遍历