最近做到二叉树的题目，准备对二叉树做一个归纳总结。首先写一下二叉树的几种遍历方法吧

1.二叉树的前序遍历：根左右 preorderTraversal 。也就是按照根-左-右的顺序，迭代来遍历一棵二叉树，用栈存储右子树，把根存储了之后，遍历左子树，然后左子树遍历完了，就从栈中弹出右子树的节点，依旧按照根左右顺序进行遍历柚子树。

leetcode 144. Binary Tree Preorder Traversal

代码如下：

/** * Definition for a binary tree node. * public class TreeNode { *     int val; *     TreeNode left; *     TreeNode right; *     TreeNode(int x) { val = x; } * } */

 

public class Solution {    public List
     
       preorderTraversal(TreeNode node) {                List
      
        list = new LinkedList
       
        ();//记录结果    Stack
        
          rights = new Stack
         
          (); //将右子树压栈    while(node!=null){        list.add(node.val);        if(node.right!=null) rights.push(node.right);        node = node.left;        if(node==null&&!rights.isEmpty()){            node = rights.pop();        }    }    return list;                }}
         
        
       
      
     

  2.二叉树的中序遍历  左右根的顺序遍历。就是先遍历完左子树，然后遍历根，最后是右子树

/**

* Definition for a binary tree node.

* public class TreeNode {

* int val;

* TreeNode left;

* TreeNode right;

* TreeNode(int x) { val = x; }

* }

*/

public class Solution {

public List<Integer> inorderTraversal(TreeNode root) {

List<Integer> res = new ArrayList<>();

Stack<TreeNode> sta = new Stack<>();

while(root!=null||!sta.isEmpty()){

while(root!=null){

sta.push(root);

root = root.left;

}

root = sta.pop();

res.add(root.val);

root =root.right;

}

return res;

}

}

3.后序遍历 postorder traversal   左 右 根的顺序来遍历

/** * Definition for a binary tree node. * public class TreeNode { *     int val; *     TreeNode left; *     TreeNode right; *     TreeNode(int x) { val = x; } * } */public class Solution {    public List
     
       postorderTraversal(TreeNode root) {                LinkedList
      
        ans = new LinkedList<>();    Stack
       
         stack = new Stack<>();    if (root == null) return ans;        stack.push(root);    while (!stack.isEmpty()) {        TreeNode cur = stack.pop();        ans.addFirst(cur.val);        if (cur.left != null) {            stack.push(cur.left);        }        if (cur.right != null) {            stack.push(cur.right);        }     }    return ans;            }}
       
      
     

如果不使用linkedlist 则：

/**      *       * @param root 树根节点      * 后序遍历不同于先序和中序，它是要先处理完左右子树，然后再处理根(回溯)，所以需要一个记录哪些节点已经被访问的结构(可以在树结构里面加一个标记)，这里可以用map实现      */      public static void postOrderStack(Node root){          if(root==null)return;          Stack
     
       s=new Stack
      
       ();          Map
       
         map=new HashMap
        
         ();           s.push(root);          while(!s.isEmpty()){              Node temp=s.peek();              if(temp.left!=null&&!map.containsKey(temp.left)){                  temp=temp.left;                  while(temp!=null){                      if(map.containsKey(temp))break;                      else s.push(temp);                      temp=temp.left;                  }                  continue;              }              if(temp.right!=null&&!map.containsKey(temp.right)){                  s.push(temp.right);                  continue;              }              Node t=s.pop();              map.put(t,true);              System.out.println(t.value);          }      }
        
       
      
     

 

 

以上均为迭代的方法。