/**
     * 前序遍历（根左右）
     * output:A、B、D、G、H、C、E、I、F
     * @param root
     */
public void preOrder(TreeNode root) {

  if (root == null) {
    return;
  } else {
    System.out.println("preOrder data:" + root.getData());
    preOrder(root.leftChild);
    preOrder(root.rightChild);
  }
}

/**
     * 中序遍历（左根右）
     * output:G、D、H、B、A、E、I、C、F
     * @param root
     */
public void midOrder(TreeNode root) {

  if (root == null) {
    return;
  } else {
    midOrder(root.leftChild);
    System.out.println("midOrder data:" + root.getData());
    midOrder(root.rightChild);
  }
}

/**
* 后序遍历（左右根）
* output:G、H、D、B、I、E、F、C、A
* @param root
*/
public void postOrder(TreeNode root){

  if (root == null) {
    return;
  } else {
    postOrder(root.leftChild);
    postOrder(root.rightChild);
    System.out.println("postOrder data:" + root.getData());
  }
}

/**
* 前序遍历非递归算法
  * output:A-B-D-E-C-F
    * @param root
    */
public void preOrderNonRecursive(TreeNode root) {

  Stack<TreeNode> nodeStack = new Stack<>();
  nodeStack.push(null);
  while (root != null) {
    // 访问根结点
    System.out.println("preOrderNonRecursive data:" + root.getData());
    // 当前结点右子树不为空则放入栈中
    if (root.rightChild != null)
      nodeStack.push(root.rightChild);
    // 访问左子树
    if (root.leftChild != null)
      root = root.leftChild;
    else root = nodeStack.pop();
  }
}

/**
* 中序遍历非递归算法
  * output:D-B-E-A-F-C
    * @param root
    */
public void midOrderNonRecursive(TreeNode root) {

  Stack<TreeNode> nodeStack = new Stack<>();
  do {
    while (root != null) {
      nodeStack.push(root);
      root = root.leftChild;
    }

    if (!nodeStack.empty()) {
      root = nodeStack.pop();
      System.out.println("preOrderNonRecursive data:" + root.getData());
      root = root.rightChild;
    }
  } while (root != null || !nodeStack.empty());
}

/**
* 后序遍历非递归算法
  * output:D-E-B-F-C-A
    *
    * @param root
    */
public void postOrderNonRecursive(TreeNode root) {

  Stack<TreeNode> nodeStack = new Stack<>();
  // 上一个结点
  TreeNode prev = root;
  do {
    while (root != null) {
      nodeStack.push(root);
      root = root.leftChild;
    }

    // 访问当前结点的右结点
    if (!nodeStack.empty()) {
      // 获取右子树，但先不弹出
      TreeNode temp = nodeStack.peek().rightChild;
      // 不存在右子树或右子树已经访问过，可以访问父结点
      if (temp == null || temp == prev) {

        root = nodeStack.pop();
        System.out.println("postOrderNonRecursive data:" + root.getData());
        // 记录访问过的结点
        prev = root;
        // 当前结点置空
        root = null;
      } else {
        // 存在右子树，需要优先访问右子树
        root = temp;
      }
    }
  } while (root != null || !nodeStack.empty());
}

/**
* 求二叉树的深度（高度）
  *
  * @return
  */
public int getHeight() {
  return getHeight(root);
}

/**
* 求二叉树的深度（高度）
  *
  * @param root
  * @return
  */
private int getHeight(TreeNode root) {
  if (root == null) {
    return 0;
  } else {
    int i = getHeight(root.leftChild);
    int j = getHeight(root.rightChild);
    return i >= j ? i + 1 : j + 1;
  }
}

/**
  * 求二叉树的结点数
  *
  * @return
  */
public int getSize() {
  return getSize(root);
}

/**
* 求二叉树的结点数
  *
  * @param root
  * @return
  */
private int getSize(TreeNode root) {

  if (root == null) {
    return 0;
  } else {
    return 1 + getSize(root.leftChild) + getSize(root.rightChild);
  }
}

// 结点类
public class TreeNode {
        int val = 0;
        TreeNode left = null;
        TreeNode right = null;
    
        public TreeNode(int val) {
            this.val = val;
        }
    }

public class CreateBinaryTree {
    // 前序遍历测试
    public static void main(String[] args) {
        TreeNode node = CreateBinaryTree.createBT(new int[]{1, 2, 3, 4, 5,6}, 0);
        CreateBinaryTree.preOrder(node); //124536
    }
		// 构建二叉树 (完全二叉树)
    public static TreeNode createBT(int[] arr, int i) // 初始时,传入的i==0
    {
        TreeNode root = null; // 定义根节点

        if (i >= arr.length) // i >= arr.length 时,表示已经到达了根节点
            return null;

        root = new TreeNode(arr[i]); // 根节点
        root.left = createBT(arr, 2 * i + 1); // 递归建立左孩子结点
        root.right = createBT(arr, 2 * i + 2); // 递归建立右孩子结点

        return root;
    }

    /**
     * @description: 前序遍历
     */
    public static void preOrder(TreeNode root) {

        if (root == null) {
            return;
        } else {
            System.out.println("preOrder data:" + root.val);
            preOrder(root.left);
            preOrder(root.right);
        }
    }
}

/**
* 层序遍历
*
* @param root
*/
public List<List<String>> levelOrder(TreeNode root) {

  List<List<String>> reList = new ArrayList<>();
  Queue<TreeNode> nodeQueue = new LinkedList<>();
  // 压入根结点
  nodeQueue.offer(root);
  while (!nodeQueue.isEmpty()) {
    int levelSize = nodeQueue.size();
    List<String> subList = new ArrayList<>();
    while (levelSize != 0) {
      TreeNode temp = nodeQueue.poll();
      subList.add(temp.getData() + "");
      if (temp.leftChild != null) nodeQueue.offer(temp.leftChild);
      if (temp.rightChild != null) nodeQueue.offer(temp.rightChild);
      levelSize--;
    }
    reList.add(subList);
  }

  return reList;
}

/**
* 复制一棵二叉树
* @param parent
* @return
*/
public TreeNode copy(TreeNode parent){

  if(parent == null)
    return null;

  // 构造根结点
  TreeNode temp = new TreeNode(parent.getIndex(),parent.getData());

  // 递归构造左子树
  temp.leftChild = copy(parent.leftChild);

  // 递归构造右子树
  temp.rightChild = copy(parent.rightChild);

  return temp;
}

/**
* 判断两棵树是否相等
* @param s
* @param t
* @return
*/
public boolean euqal(TreeNode s,TreeNode t){

  if(s == null && t == null)
    return true;

  if(s != null && t != null && s.data == t.data &&
     euqal(s.leftChild,t.leftChild) &&
     euqal(s.rightChild,t.rightChild))
    return true;
  else
    return false;
}