package com.easy.leetcode.algorithm.leetcode144;

import java.util.ArrayList;
import java.util.List;
import java.util.Stack;

/**
 * @ Definition for a binary tree node.
 * @ public class TreeNode {
 * @ int val; TreeNode left;
 * @ TreeNode right;
 * @ TreeNode(int x) {
 * @ val = x;
 * @ }
 * @ }
 */
class Solution {

  public static void main(String[] args) {
    Solution s = new Solution();
    Solution.TreeNode root = new Solution.TreeNode(3);
    root.left = new Solution.TreeNode(9);
    root.right = new Solution.TreeNode(20);
    /*Solution.TreeNode left = root.left;
    left.left = new Solution.TreeNode(1);
    left.right = new Solution.TreeNode(2);
    Solution.TreeNode right = root.right;
    right.left = new Solution.TreeNode(15);
    right.right = new Solution.TreeNode(7);*/

    List<Integer> xx = s.preorderTraversal(root);
    System.out.println(xx);

  }

  public List<Integer> preorderTraversal(TreeNode root) {

    List<Integer> list = new ArrayList<>();
    pre(root, list);

    return list;
  }

  /**
   * @ 根左右
   * @ 递归的理解（个人觉得这个理解，可以画一个栈理解每部操作）
   * @ 不看list部分
   * @ 1。 沿着左孩子【//left】，一直递归调用，直到==null停止，一轮递归结束（注意，中间左孩子，还在栈中并未结束）
   * @ 2。 一轮结束（左孩子最后一个节点处理完，可以出栈了，也就是return），可以开始取当前node的右孩子【//right】，重复1步骤。
   * @ 3。 ==null后，当前node也开始出栈，原栈中数据可以开始继续执行【//right部分】，直到==null结束。
   */
  public void pre(TreeNode node, List<Integer> list) {
    if (node == null) {
      return;
    }
    list.add(node.val); // list
    pre(node.left, list); // left
    pre(node.right, list); // right

  }

  /**
   * @ 循环以及栈的应用（大体和递归思路很像）
   * @ 核心：栈操作，实际模拟了递归JVM栈的方式
   * @ // 1. 外层循环树，栈不是空（注意：因为栈是辅助工具，所以必须保证最后栈中是没有数据的）
   * @ // 2. 内层循环，类似递归的1，也是不断循环左孩子[//left]，一直入栈[//push]，直到==null,跳出内层循环
   * @ // 3. 栈中目前存储都是未处理完的左孩子（为什么说未处理完，因为他们还有右节点未处理），
   * @ // 4. 所以下面开始继续外层循环，开始处理最左侧的叶子节点[//pop]（2循环到的最后一个节点），
   * @ // 5. 继续4的右孩子的内层循环,反复2，3，4
   * @
   * @ 总结：内部循环实际就相当于递归的JVM的入栈操作，而外层循环就是递归的一层调用结束（遇到node==null）,
   * @ 这就是JVM需要出栈，然后执行原来已经压入栈的数据。
   * @
   */
  public void preWhile(TreeNode node, List<Integer> list) {
    Stack<TreeNode> stack = new Stack<>();

    while (node != null || !stack.isEmpty()) {
      while (node != null) {
        list.add(node.val);
        stack.push(node); // push
        node = node.left; // left
      }
      node = stack.pop();//pop
      node = node.right; // right
    }

  }


  static class TreeNode {

    int val;
    TreeNode left;
    TreeNode right;

    TreeNode(int x) {
      val = x;
    }
  }
}