算法 二叉树的各种遍历

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

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

/**
 * 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]
]

本题的描述比一般的层次遍历更复杂一些，不但要层次遍历，还要每个层单独的一个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测试并通过。