、二叉树

对于每次递归遍历的时候，会产生一个遍历序，也就是对于一个节点间，会进行三次访问

可以在这三次中改变打印的位置。从而形成先序，中序，后序遍历。

代码：

public static void OrderRecur(Node head) {
		if (head == null) {
			return;
		}
		//第一次访问节点就输出，System.out.print(head.value + " ");
		OrderRecur(head.left);
   		 //第二次访问节点输出 System.out.print(head.value + " ");
		OrderRecur(head.right);
   		 //第三次访问节点输出System.out.print(head.value + " ");
	}

非递归遍历

先序

/**
 * 准备一个栈，将root压入栈

 * 1.弹出栈元素

 * 2.打印
 * 3.先压入右节点，再压入左节点（如果有的话）
 * 4.循环上述步骤
 * @param root
 */
public static void PreOrderWithoutRecursion(Node root){
    //栈
    Stack<Node> nodes = new Stack<>();
    nodes.push(root);
    while (!nodes.isEmpty()){
        //弹出
        Node pop = nodes.pop();
        System.out.println(pop.value);
        //压入孩子节点
        if (pop.right != null){
            nodes.push(pop.right);
        }
        if (pop.left != null){
            nodes.push(pop.left);
        }
    }
}

中序

/**
 * 准备一个栈，将root压入栈

 * 1.一直将节点的左孩子压入栈中
 * 2.弹出打印
 * 3.如果弹出的存在右孩子，也将右孩子的左孩子一直压入栈
 * 4，循环

 */
public static void InOrderWithoutRecursion(Node root){
    //栈
    Stack<Node> nodes = new Stack<>();
    while (! nodes.isEmpty() || root != null){
        //1.将左孩子全部压入栈中
        if (root != null){
            nodes.push(root);
            root = root.left;
        }
        else {
            //2.弹出，打印
            root = nodes.pop();
            System.out.print(root.value+" ");
            //继续右孩子
            root = root.right;
        }
    }
}

后续

/**
     * 准备两个栈，将root压入栈

     * 1.弹出，压入到2栈中
     * 2.将左孩子压入1栈

     * 3.将右孩子压入1栈

     * 4.一直到1栈为空，输出2栈元素

     */
public static void PosOrderWithoutRecursion(Node root){
    Stack<Node> stack1 = new Stack<>();
    Stack<Node> stack2 = new Stack<>();
    stack1.push(root);

    while (!stack1.isEmpty()){
        //弹出，压缩2栈
        Node pop = stack1.pop();
        stack2.push(pop);
        //分别压入左孩子和有孩子
        if (pop.left != null){
            stack1.push(pop.left);
        }
        if (pop.right != null){
            stack1.push(pop.right);
        }
    }
    while ( !stack2.isEmpty()){
        Node pop = stack2.pop();
        System.out.print(pop.value+" ");
    }
}

层次

/**
 * 层次遍历
 * 准备一个队列 ，加入根节点
 * 1，弹出，打印
 * 2.加入左孩子

 * 3.加入右孩子

 * 4.循环
 */
public static void WithOrder(Node root){
    Queue<Node> queue = new LinkedList<>();
    queue.add(root);
    while (!queue.isEmpty()){
        //弹出打印
        Node poll = queue.poll();
        System.out.print(poll.value+" ");
        if (poll.left != null){
            queue.add(poll.left);
        }
        if (poll.right != null){
            queue.add(poll.right);
        }
    }
}

题

获取最大宽度

使用层次遍历

/**
 * 获取最大宽度 将根节点加入到队列中
 * 准备一个队列，准备一个hashMap,用来存储各个节点处于第几层

 * 1.先层次遍历，在添加节点，要向map中添加节点处在都第几层

 * 2.在层次遍历中，如果发现节点的层数和要统计的层数相同，就当前层数节点数++，并将最大值保留

 *  不同则说明已经统计到下一层了，将统计的层数更新，将当前节点数更新
 */
public static int getMaxWith(Node root){
    Queue<Node> queue = new LinkedList<>();
    //各个节点的层数
    Map<Node, Integer> map = new HashMap<>();
    queue.add(root);
    //root在第一层
    map.put(root,1);
    //当前层数
    int curLevel = 1;
    //当前层数的节点
    int curLevelNodes = 0;
    //最大值
    int max = Integer.MIN_VALUE;
    while (!queue.isEmpty()){
        Node poll = queue.poll();
        int curNodeLevel = map.get(poll);
        //当前节点的层数等于当前层数
        if (curNodeLevel == curLevel){
            //节点数++
            curLevelNodes++;
        }
        //已经到下一层
        else {
            //更新max
            max = Math.max(max,curLevelNodes);
            //更新层数
            curLevel++;
            //初始化当前层数节点数
            curLevelNodes = 1;
        }
        if (poll.left != null){
            map.put(poll.left, curLevel+1);
            queue.add(poll.left);

        }
        if (poll.right!= null){
            map.put(poll.right, curLevel+1);
            queue.add(poll.right);
        }
    }
    max = Math.max(curLevelNodes,max);
    return max;
}

判断是否为搜索二叉树（左子树值小于根小于右子树）

中序遍历改写

判断是否为完全二叉树

/**
 * 判断是否为完全二叉树
 * 满足两个条件
 * 使用层次遍历
 * 1.如果节点有右孩子没有左孩子，则不是

 * 2.如果不是孩子双全，并且满足第一个条件，那么接下来的节点就都是叶子节点

 * @return
 */
public static boolean isCompletedBinaryTree(Node root){
    Queue<Node> queue = new LinkedList<>();
    queue.add(root);
    Node leftChird = null;
    Node rightChird = null;
    //是否是孩子双全
    boolean sigleChild = false;
    while (! queue.isEmpty()){
        Node poll = queue.poll();
        leftChird = poll.left;
        rightChird = poll.right;
        //如果满足了第一个条件，并且当前节点不是叶节点
        //或 只有右孩子没有左孩子,
        //则不是完全二叉树
        if (sigleChild && (leftChird != null || rightChird!= null)
                ||
                (rightChird != null && leftChird == null)){
            return false;
        }
        if (leftChird != null){
            queue.add(leftChird);
        }
        if (rightChird != null){
            queue.add(rightChird);
        }
        //如果孩子不双全,则变为单个节点的状态
        if (leftChird == null || rightChird == null){
            sigleChild = true;
        }
    }
    return true;

}

判断是否为平衡二叉树（模板,递归）

/**
 * 是否是平衡二叉树
 * 平衡二叉树：左子树是平衡二叉树，右子树是平衡二叉树，子树的高度差小于2
 * 因此对于子树而言，需要返回两个值，是否是平衡树，以及高度

 */
public static ResultType process(Node node){
    if (node == null){
        return new ResultType(true,0);
    }
    ResultType leftResult = process(node.left);
    ResultType rightResult = process(node.right);
    //高度
    int height = Math.max(leftResult.height, rightResult.height)+1;
    //平衡
    boolean isBlance = Math.abs(leftResult.height- rightResult.height) < 2;
    return new ResultType(isBlance,height);
}
public static boolean isBalanceBinaryTreeRecursion(Node root){
    ResultType process = process(root);
    return process.isBlance;
}
//返回结果封装
public static class ResultType {
    //是否平衡
    private boolean isBlance;
    //高度
    private int height;

    public ResultType(boolean isBlance, int height) {
        this.isBlance = isBlance;
        this.height = height;
    }
}

判断是否为满二叉树（模板，递归）

/**
 * 判断是否为满二叉树

 * 模板：得到height,nodes
 * (2^height)- 1 = nodes
 */
public static boolean isFullBinaryTree(Node root){
    if (root == null){
        return true;
    }
    ResultData resultData = f(root);
    int height = resultData.height;
    int nodes = resultData.nodes;
    boolean isFull = (1 << height)-1 == nodes;
    return isFull;
}
public static ResultData f(Node node){
    if (node == null){
        //空树高度0，节点数0
        return new ResultData(0,0);
    }
    ResultData leftRes = f(node.left);
    ResultData ritRes = f(node.right);
    int height = Math.max(leftRes.height, ritRes.height);
    int nodes = leftRes.nodes+ ritRes.nodes;
    return new ResultData(height,nodes);
}
//满二叉树封装结果
public static class ResultData{
    private int height;
    private int nodes;

    public ResultData(int height, int nodes) {
        this.height = height;
        this.nodes = nodes;
    }
}

最低公共祖先节点

给定两个二叉树的节点node1和node2，找到他们的最低公共祖先节点

/**
 * 准备一个map,存储各个节点的父节点
 * 准备一个set,将n1链的父节点进行存储

 * 遍历n2的父节点过程中，如果在set中存在，则直接返回该点就是最终lca
 */
public static Node LCA(Node root,Node n1,Node n2){
    //存放对应父节点
    HashMap<Node,Node> map = new HashMap<>();
    map.put(root,root);
    process(root,map);
    //存放n1的父节点链
    HashSet<Node> set = new HashSet<>();
    Node cur1 = n1;
    Node cur2 = n2;
    //一直到根节点
    while (cur1 != map.get(cur1)){
        set.add(cur1);
        cur1 = map.get(cur1);
    }
    //加入根节点
    set.add(root);
    //在链中找n2的父节点们
    while (!set.contains(cur2)){
        cur2 = map.get(cur2);
    }
    return cur2;
}
//存储父节点
public static void process(Node node, HashMap<Node,Node> map){
    if (node == null){
        return;
    }
    //添加父节点
    map.put(node.left,node);
    map.put(node.right,node);
    process(node.left,map);
    process(node.right,map);
}

方法二

/**
 * lca方法二

 * 对于每一个节点来说

 * 如果左右子树中存在n1或n2则返回

 * 不存在则返回空

 * 到根节点的时候，也就是回溯到最上层时候，如果左子树不存在n1和n2，那么返回右子树最先出现的n1或n2就是lca
 * 如果n1和n2分别出现在左右子树

 * 那么根节点就是lca
 */
public static Node LCA2(Node root,Node n1,Node n2){
    if (root == null || root == n1 || root == n2){
        return root;
    }
    //寻找孩子
    Node left = LCA2(root.left, n1, n2);
    Node right = LCA2(root.right, n1, n2);
    //如果n1和n2是两个分支中
    if (left != null && right != null){
        return root;
    }
    return left!=null?left:right;
}

折纸问题

请把一段纸条竖着放在桌子上，然后从纸条的下边向上方对折1次，压出折痕后展开。

此时折痕是凹下去的，即折痕突起的方向指向纸条的背面。如果从纸条的下边向上方连续对折2次，压出折痕后展开，此时有三条折痕，从上到下依次是下折痕、下折痕和上折痕。

给定一个输入参数N，代表纸条都从下边向上方连续对折N次。

请从上到下打印所有折痕的方向。

例如:N=1时，打印: down N=2时，打印: down down up

public static void main(String[] args) {
    int N = 3;
    paperFold(N);
}
public static void process(int level,int N, boolean down){
    if (level > N){
        return;
    }
    process(level+1,N,true);
    System.out.println(down?"down":"up");
    process(level+1,N,false);
}
public static void paperFold(int N){
    process(1,N,true);
}