public void preorder_Traversal(TreeNode root)
  {
    if(root==null)return;
    
    //訪問(wèn)節(jié)點(diǎn)的邏輯代碼塊
    System.out.print(root.val+" ");
    
    preorder_Traversal(root.left);
    preorder_Traversal(root.right);
  }

public void preorder(TreeNode root)
  {
    Stack<TreeNode>  stack=new Stack<>();
    while(root!=null||!stack.isEmpty())
    {
      //當(dāng)前節(jié)點(diǎn)不為空，則入棧，確保最后遍歷到的節(jié)點(diǎn)沒(méi)有左子節(jié)點(diǎn)
      //因?yàn)槭乔靶虮闅v，所以再遍歷到每個(gè)節(jié)點(diǎn)的時(shí)候，都可以先訪問(wèn)，再尋找其左右子節(jié)點(diǎn)。
      while(root!=null)
      {
        System.out.print(root.val+" ");
        stack.push(root);
        root=root.left;
      }
      if(!stack.empty())
      {
        //把這兩步看成是一步，找到右節(jié)點(diǎn)，并把已處理的中節(jié)點(diǎn)從stack當(dāng)中去除
        root=stack.pop();
        root=root.right;
      }
    }
  }

public void inorder_Traversal(TreeNode root)
  {
    if(root==null)return;
    inorder_Traversal(root.left);
    
     //訪問(wèn)節(jié)點(diǎn)的邏輯代碼塊
    System.out.print(root.val+" ");
    
    inorder_Traversal(root.right);
  }

public void Inorder(TreeNode root)
  {
    Stack<TreeNode> stack=new Stack<>();
    while(root!=null||!stack.isEmpty())
    {
      //當(dāng)前節(jié)點(diǎn)不為空，則入棧，確保最后遍歷到的節(jié)點(diǎn)沒(méi)有左子節(jié)點(diǎn)
      while(root!=null)
      {
        stack.push(root);
        root=root.left;
      }
      //通過(guò)當(dāng)前節(jié)點(diǎn)，跳到當(dāng)前節(jié)點(diǎn)的右節(jié)點(diǎn)，因?yàn)槭侵行虮闅v，所以當(dāng)前節(jié)點(diǎn)沒(méi)有左節(jié)點(diǎn)的時(shí)候，就 
       可以訪問(wèn)當(dāng)前節(jié)點(diǎn)
      if(!stack.empty())
      {
        root=stack.pop();
        System.out.print(root.val+" ");
        root=root.right;
      }
    }
  }

public void postorder_Traversal(TreeNode root)
  {
    if(root==null)return;
    postorder_Traversal(root.left);
    postorder_Traversal(root.right);
    
     //訪問(wèn)節(jié)點(diǎn)的邏輯代碼塊
    System.out.print(root.val+" ");
  }

public void Postorder(TreeNode root)
  {
    Stack<TreeNode> s =new Stack<>(); 
    Stack<Integer> s2 =new Stack<>();
    Integer i=new Integer(1);
    while(root!=null||!s.isEmpty())
    {
      //只要當(dāng)前節(jié)點(diǎn)非空，就入棧
      while(root!=null)
      {
        s.push(root);
        s2.push(new Integer(0));
        root=root.left;
      }
      //s2當(dāng)中如果存1，則意味著當(dāng)前s1對(duì)應(yīng)的節(jié)點(diǎn)的左右子節(jié)點(diǎn)都已經(jīng)遍歷過(guò)了。
      while(!s.empty()&&s2.peek().equals(i))
      {
        s2.pop();
        System.out.print(s.pop().val+" ");
      }
      if(!s.isEmpty())
      {
        s2.pop();
        s2.push(new Integer(1));
        root=s.peek();
        root=root.right;
      }
      
    }
  }

public void postOrder(Node root) {
		
	Stack<Node> s = new Stack<Node>();
	Node p = root;
	while (p != null || !s.empty()) {
		while(p != null) {
			s.push(p);
			p = p.left;
		}
		p = s.pop();
		System.out.print(p.val+" ");
	//這里需要判斷一下，當(dāng)前p是否為棧頂?shù)淖笞訕?，如果是的話那么還需要先訪問(wèn)右子樹才能訪問(wèn)根節(jié)點(diǎn)
	//如果已經(jīng)是不是左子樹的話，那么說(shuō)明左右子書都已經(jīng)訪問(wèn)完畢，可以訪問(wèn)根節(jié)點(diǎn)了，所以講p復(fù)制為NULL
	//取根節(jié)點(diǎn)
		if (!s.empty() && p == s.peek().left) {
			p = s.peek().right;
		}
		else p = null;
	}
}
 

public void LaywerTraversal(TreeNode root){
  if(root==null) return;
  LinkedList<TreeNode> list = new LinkedList<TreeNode>(); 
  list.add(root);
  TreeNode currentNode;
  while(!list.isEmpty()){
    currentNode=list.poll();
    System.out.println(currentNode.val);
    if(currentNode.left!=null){
      list.add(currentNode.left);
    }
    if(currentNode.right!=null){
      list.add(currentNode.right);
    }
  }
}