Binary Tree Preorder Traversal @leetcode

在二叉樹方面停留了好長一段時間，各種資料:維基百科的定義、csdn的部落格，java的api使用方法視訊，最近突然發現我對資料結構的了解似乎開始有點質變的現象啦，開始能自己寫出完整正确的代碼啦，欣喜中，再接再厲，為自己加油！今天來貼一段二叉樹遞歸實作先序周遊的完整代碼。

      leetcode原題位址：https://oj.leetcode.com/problems/binary-tree-preorder-traversal/

  解題思路：

題目雖然是建議不用遞歸算法，因目前還沒開始學習疊代的算法思想，是以先暫時用遞歸思想來解。

要實作先序周遊，是以完整程式包含如下幾點

1、建立二叉樹  public void createBinaryTree(TreeNode root){}

2、二叉樹是由結點構成的（即TreeNode），是以建立個TreeNode 類，即 public  class TreeNode{}

3、從維基百科裡了解到二叉樹結點通常通過數組或者線性表來存儲，我這裡采用數組來存儲結點，即ArrayList<Integer>，是以開頭要import java.util.ArrayList;

4、前3個步驟完成之後，現在可以建立先序周遊方法啦，剛剛第3步說用ArrayList來存儲二叉樹結點，是以這麼寫先序周遊方法 public ArrayList<Integer> inordertraversal(TreeNode root){}，該方法内的思想要展現出先序周遊的邏輯：通路根節點--》通路左孩子--》通路右孩子

package tree;

import java.util.ArrayList;

public class Preorder_traversal {
	private TreeNode root = null;
	private ArrayList<Integer> res;
	
	public Preorder_traversal(){
		root = new TreeNode(1,1);
	} 
	
	//建立二叉樹
	public void createBinaryTree(TreeNode root){
		TreeNode newNodeB = new TreeNode(2,2);
		TreeNode newNodeC = new TreeNode(3,3);
		root.rightChild = newNodeB;
		root.rightChild.leftChild = newNodeC;
		
	}
	
	//二叉樹由結點構成,是以需要建立TreeNode類
	public class TreeNode{
		private int key = 0;
		private int data = 0;
		private TreeNode leftChild = null;
		private TreeNode rightChild = null;
		
		public TreeNode(int key,int data){
			this.key =  key;
			this.data = data;
			this.leftChild = null;
			this.rightChild = null;
		}
	}
	
	//二叉樹結點通常用數組或線性表進行存儲，這裡選擇使用數組ArrayList才存儲
	public ArrayList<Integer> preorder_Traversal(TreeNode root){
		res = new ArrayList<Integer>();
		helper(root,res);
		return res;
	}
	
	public void helper(TreeNode root,ArrayList<Integer> res){
		if (root == null)
			return ;
		else {
			//helper(root,res);
			res.add(root.data);
			helper(root.leftChild,res);
			helper(root.rightChild,res);
		}
	}
	
	public static void main(String[] args){
		Preorder_traversal bt = new Preorder_traversal();
		bt.createBinaryTree(bt.root);
		bt.preorder_Traversal(bt.root);
		int count = bt.res.size();
		for (int i=0;i<count;i++){
			System.out.print(bt.res.get(i)+" ");
		}
	}
}
           

列印結果如下：

1 2 3