package shujujiegou.二叉树;

import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Stack;

/**

• 实现

• 前序遍历

• 中序遍历

• 后序遍历
  */
  public class TreeNodeMain {
  public static void main(String[] args) {
  LinkedList<Integer> linkedList = new LinkedList<>(
  Arrays.asList(new Integer[]{
  3, 2, 9, null, null, 10, null, null, null, 8, null, 4
  })
  );
  TreeNode treeNode = createBinaryTree(linkedList);

   preOrderTraveal(treeNode);
   System.out.println("前序遍历");
  
   inOrderTraveral(treeNode);
   System.out.println("中序遍历");
  
   postOrderTraveral(treeNode);
   System.out.println("后序遍历");
  
   postOrderTraveralWithStacj(treeNode);
   System.out.println("非递归前序遍历");
  
   postOrdeTraveralWithMid(treeNode);
   System.out.println("非递归中序遍历");
  
   postOrdeTraveralWithLast(treeNode);
   System.out.println("非递归后序遍历");
  
  
   postOrderTraversal(treeNode);
   System.out.println("层序遍历");
  

  }

/**
 * 构建二叉树
 *
 * @param inputList
 * @return
 */
private static TreeNode createBinaryTree(LinkedList<Integer> inputList) {
    TreeNode node = null;
    if (inputList == null || inputList.isEmpty()) {
        return null;
    }
    Integer data = inputList.removeFirst();
    //如果元素 为空 则不在进行遍历
    if (data != null) {
        node = new TreeNode(data);
        node.leftChild = createBinaryTree(inputList);
        node.rightChild = createBinaryTree(inputList);
    }
    return node;
}

/**
 * 二叉树前序遍历
 *
 * @param node
 */
private static void preOrderTraveal(TreeNode node) {
    if (node == null) {
        return;
    }
    System.out.print(node.data);
    preOrderTraveal(node.leftChild);
    preOrderTraveal(node.rightChild);
}

/**
 * 二叉树中序遍历
 *
 * @param node
 */
private static void inOrderTraveral(TreeNode node) {
    if (node == null) {
        return;
    }
    inOrderTraveral(node.leftChild);
    System.out.print(node.data);
    inOrderTraveral(node.rightChild);
}

/**
 * 二叉树后序遍历
 *
 * @param node
 */
private static void postOrderTraveral(TreeNode node) {
    if (node == null) {
        return;
    }
    postOrderTraveral(node.leftChild);
    postOrderTraveral(node.rightChild);
    System.out.print(node.data);
}

/**
 * 二叉树非递归前序遍历
 */
private static void postOrderTraveralWithStacj(TreeNode root) {
    Stack<TreeNode> stack = new Stack<>();
    TreeNode treeNode = root;
    while (treeNode != null || !stack.isEmpty()) {
        //迭代访问节点的左孩子，并入栈
        while (treeNode != null) {
            System.out.print(treeNode.data);
            stack.push(treeNode);
            treeNode = treeNode.leftChild;
        }
        //如果节点没有左孩子，则弹出栈顶节点，访问右孩子
        if (!stack.isEmpty()) {
            treeNode = stack.pop();
            treeNode = treeNode.rightChild;
        }
    }
}

/**
 * 非递归 二叉树 中序遍历
 *
 * @param root
 */
private static void postOrdeTraveralWithMid(TreeNode root) {
    //栈
    Stack<TreeNode> stack = new Stack<>();
    TreeNode treeNode = root;
    while (treeNode != null || !stack.isEmpty()) {
        while (treeNode != null) {

            stack.push(treeNode);
            treeNode = treeNode.leftChild;

        }
        if (!stack.isEmpty()) {
            treeNode = stack.pop();
            System.out.print(treeNode.data);
            treeNode = treeNode.rightChild;
        }

    }
}

/*
非递归 二叉树 后序遍历
 */
private static void postOrdeTraveralWithLast(TreeNode root) {
    if (root == null) {
        System.out.println("空树");
    }
    TreeNode temp = root;
    TreeNode pre = null;
    Stack<TreeNode> stack = new Stack<>();
    while (temp != null || !stack.isEmpty()) {
        while (temp != null) {
            stack.push(temp);
            temp = temp.leftChild;
        }
        if (!stack.isEmpty()) {
            temp = stack.peek();
            if (temp != null) {
                if (temp.rightChild == null || temp.rightChild == pre) {
                    temp = stack.pop();
                    System.out.print(temp.data);
                    pre = temp;
                    temp = null;
                } else {
                    temp = temp.rightChild;
                }
            }
        }
    }
}

private static void postOrderTraversal(TreeNode treeNode) {
    Queue<TreeNode> queue = new LinkedList<>();
    //入队
    queue.offer(treeNode);
    while (!queue.isEmpty()) {
        if (!queue.isEmpty()) {
            //出队
            TreeNode node = queue.poll();
            System.out.print(node.data);

            if (node.leftChild != null) {
                queue.offer(node.leftChild);
            }
            if (node.rightChild != null) {
                queue.offer(node.rightChild);
            }
        }

    }
}

}