76.Binary Tree Inorder Traversal

Given a binary tree,return the インディーズ trversal 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;
		}else{
			list.addAll(inorderTraversal(root.left));
			list.add(root.val);
			list.addAll(inorderTraversal(root.right));
		}
		return list;

    }

方法の2:反復の思想を採用して、順番に二叉の木を遍歴します.
チェーンとスタックを利用して、nodeはスタックの要素を表しています.一番左の枝のすべての左の子供をスタックに入れて、ポップアップの要素popnodeは結果listに参加する必要があります.そしてpopnodeは右の子供がいるかどうかを判断します.あれば、その右の子供をnodeとしてスタックに入れます.サイクルを続けます

/**
	 *                。（      ）
	 * @param root
	 * @return
	 */
	public List<Integer> inorderTraversal2(TreeNode root) {
		List<Integer> list = new ArrayList<Integer>();
		if(root == null){
			return list;
		}else{
			TreeNode node = root; 
			Stack stack = new Stack();
			stack.push(node);
			/*node       ，popnode       */
			while(!stack.isEmpty()){
				while(node.left != null){//      ，           。
					node = node.left;
					stack.push(node);			
				}
				TreeNode popnode= (TreeNode) stack.pop();//      
				list.add(popnode.val);
				/*           ，        ，       */
				if(popnode.right != null){
					node = popnode.right;
					stack.push(node);
				}
			}
		}
		return list;
	}
	
	/**
	 *       。 
	 *          。
	 */
	public List<Integer> inorderTraversal3(TreeNode root){
		List<Integer> list = new ArrayList<Integer>();
		if(root == null){
			return list;
		}else{
			TreeNode node = root; 
			Stack stack = new Stack();
			stack.push(node);
			/*node       ，popnode       */
			while(!stack.isEmpty()){
				if(node.left != null){
					node = node.left;
					stack.push(node);
				}else{
					TreeNode popnode= (TreeNode) stack.pop();//      
					list.add(popnode.val);
					/*           ，        ，       */
					if(popnode.right != null){
						node = popnode.right;
						stack.push(node);
					}
				}
			}
		}
		return list;
	}

似たようなテーマは二叉樹の前の順序でいっぱいです.http://blog.csdn.net/u010339647/article/details/50505831