算法之dfs

1）之前涉及dfs，用递归比较多，但是若递归次数非常多，可能栈溢出，那么就需要用非递归的方式解决了，递归是jvm自动分配方法栈，那非递归可以基于自定义栈实现最终逻辑；

二叉树的中序遍历
方法一基于递归（递归次数多了，可能会引起栈溢出）

    public static List<Integer> zhongxuBianli(TreeNode root){
        List<Integer> res = new ArrayList();
        inorder(root,res);
        System.out.println(res.toString());
        return res;
    }
          //力扣，94 二叉树的中序遍历 子方法
    public static void inorder(TreeNode root ,List<Integer> list){
        if(root == null)return;
        inorder(root.left,list);
        list.add(root.val);
        inorder(root.right,list);
    }

方法二基于自定义栈（不存在栈溢出问题）

    public static List<Integer> zhongxuBianliSelfStack(TreeNode root){
        LinkedList<TreeNode> linkedList = new LinkedList();
        ArrayList<Integer> list = new ArrayList();
        while (root!=null || !linkedList.isEmpty()){
            while (root!=null){
                linkedList.push(root);
                root=root.left;
            }
            root = linkedList.pop();
            list.add(root.val);
            root=root.right;
        }
        return list;
    }

公共类

 public static class TreeNode{
        int val;
        TreeNode left;
        TreeNode right;

        public TreeNode(int val, TreeNode left, TreeNode right) {
            this.val = val;
            this.left = left;
            this.right = right;
        }
        public TreeNode(int val) {
            this.val = val;
        }
        public TreeNode() {
        }
    }

2）上述方法2稍作修改，就可以判断一棵树是否是二叉查找树，因为上边是中序遍历，如果是二叉查找树则满足升序排列，所以可以将当前pop出的一个数与前一个pop的数比较，若当前数小或等于前一个值，则直接返回false，表明当前不是二叉查找树；

 public static boolean panDuanErChaChaZhaoShu(TreeNode root){
        LinkedList<TreeNode> linkedList = new LinkedList();
        long beforeVal=Long.MIN_VALUE;
        while (root!=null || !linkedList.isEmpty()){
            while (root!=null){
                linkedList.push(root);
                root=root.left;
            }
            root = linkedList.pop();
            if(root.val <= beforeVal){
                return false;
            }
            beforeVal=root.val;
            root=root.right;
        }
        return true;
    }

3）上述方法继续变化，可以应对求二叉树最大深度问题

public static int erChaShuMaxDepth(TreeNode root){
        LinkedList<TreeNode> linkedList = new LinkedList();
        int max=0;
        TreeNode pop=null;
        while (root!=null || !linkedList.isEmpty()){
            while (root!=null){
                linkedList.push(root);
                root=root.left;
                max=Math.max(max,linkedList.size());
            }
            //这里用peek主要是如果右边有子节点则需要先看下右边子树的深度，而不能一概pop
            TreeNode peek = linkedList.peek();
            //第一个条件意思是如果右边无子节点，则直接pop当前节点
            // 第二个条件意思是如果右边是刚弹出的子节点，则表明是已经计算过深度的，可以直接pop当前节点
            if(peek.right ==null || peek.right == pop){
                pop = linkedList.pop();
            }else{
            //如果右边子节点存在且还没有遍历过，则更新root，准备下一轮循环放入栈中
                root=peek.right;
            }
        }
        return max;
    }

4）上述erChaShuMaxDepth方法其实是基于后序遍历，稍作修改即可实现二叉树的后序遍历，代码如下

  public static List<Integer> houXuBianLi(TreeNode root){
        LinkedList<TreeNode> linkedList = new LinkedList();
        ArrayList<Integer> list = new ArrayList();
        TreeNode pop=null;
        while (root !=null || !linkedList.isEmpty()){
            while (root!=null){
                linkedList.push(root);
                root=root.left;
            }
            TreeNode peek = linkedList.peek();
            if(peek.right==null || peek.right==pop){
                pop=linkedList.pop();
                list.add(pop.val);
            }else{
             //如果右节点存在且还未遍历，则准备进行处理
                root=peek.right;
            }
        }
        return list;
    }

或者不用peek方法，直接pop，但需要记录子节点pre，需要通过pre确认已经遍历过右子节点

			root = stack.pop();
            if (root.right == null || root.right == prev) {
                res.add(root.val);
                prev = root;
                root = null;
            } else {
                stack.push(root);
                root = root.right;
            }

前序遍历也是做一些修改

 public static List<Integer> qianXuBianLi(TreeNode root){
        LinkedList<TreeNode> linkedList = new LinkedList();
        ArrayList<Integer> list = new ArrayList();
        TreeNode pop=null;
        while (root !=null || !linkedList.isEmpty()){
            while (root!=null){
            	list.add(root.val);
                linkedList.push(root);
                root=root.left;
            }
                root=linkedList.pop();
                root=root.right;
        }
        return list;
    }