二叉树

class Tree {
	Node left;
	Node right;
	int value;
	//递归
	public static void f(Tree head) {
		if(head == null) {
		reutrn;
		}
		f(head.left);
		f(head.right);
	}
	//遍历结果
	//1，2，4，4，4，2，5，5，5，2，1，3，6，6，6，3，7，7，7，3，1
}

遍历

先序遍历

先序遍历指的是所有子树中先打印头节点、在左节点、最后右节点
头左右：：1，2，4，5，3，6，7（利用递归顺第一次出现的打印）
递归方式：

	public static void f(Tree head) {
		if(head == null) {
		reutrn;
		}
		System.out.println(head.value);
		f(head.left);
		f(head.right);
	}

非递归压栈形式可实现：
每次

1. 从栈中弹出一个节点cur
2. 打印
3. 先右后左压入（如果有）
4. 重复1

	public static void f(Tree head) {
		if(head == null) {
			return;
		}
		Stack<Node> stack = new Stack();
		stack.add(head);
		while(!stack.isEmpty()){
		Node head = stack.pop();
		System.out.print(head.value);
		if(head.right != null) {
			stack.push(head.right);
		}
		if(head.left!= null) {
			stack.push(head.left);
		}
		}
	}

中序遍历

左头右：4，2，5，1，6，3，7（利用递归顺第二次出现的打印）

	public static void f(Tree head) {
		if(head == null) {
		reutrn;
		}
		f(head.left);
		System.out.println(head.value);
		f(head.right);
	}

非递归：

1. 先将所有子树左节点放入栈中
2. 弹出打印
3. 弹出时判断是否存在右子树
4. 存在压入右节点

    public void inOrderUnRecur(Node head) {
        if (head == null) {
            return;
        }
        Stack<Node> stack = new Stack<Node>();
        while (!stack.isEmpty() || head != null) {
            if (head != null) {
                stack.push(head);
                head = head.left;
            } else {
                head = stack.pop();
                System.out.println(head.value);
                head = head.right;
            }
        }
    }

后序遍历

左右头：4，5，2，6，7，3，1（利用递归顺第三次出现的打印）

	public static void f(Tree head) {
		if(head == null) {
		reutrn;
		}
		f(head.left);
		f(head.right);
		System.out.println(head.value);
	}

非递归：

1. 申请1个栈、1个收集栈
2. 放入头cur 弹出放入收集栈
3. 先左在右放入（如果右）
4. 弹出
5. 遍历收集栈

	public static void f(Tree head) {
		if(head == null) {
			return;
		}
		Stack<Node> s1= new Stack();
		Stack<Node> s2 = new Stack();
		stack.push(head);
		while(!s1.isEmpty()){
		 head = s1.pop();
		  s2.push(head);
			if(head.left!= null) {
			stack.push(head.right);
		}
		if(head.right != null) {
			stack.push(head.right);
		}
		}
		while(!s2.isEmpty()){
		System.out.println(s2.pop().value);
		}
	}

深度遍历

二叉树的深度遍历即为先序遍历。

广度遍历（宽度遍历）

用队列先左在右放入取出即可

    public static void f(Node head) {
        if(head == null) {
            return;
        }
        Queue<Node> queue = new LinkedList<Node>();
        queue.add(head);
        while(!queue.isEmpty()){
            head= queue.poll();
            System.out.print(head.value);
            if(head.left!= null) {
                queue.add(head.left);
            }
            if(head.right!= null) {
                queue.add(head.right);
            }
        }
    }

计算当前树最大宽度是多少

   public static int w(Node head) {
        if(head == null) {
            return 0;
        }
        Queue<TreeNode> queue = new LinkedList<TreeNode>();
        queue.add(head);
        //记录节点个数
        Map<TreeNode, Integer> levelMap = new HashMap<>();
        levelMap.put(head,1);
        //当前最大个数
        int max = Integer.MIN_VALUE;
        //当前层数
        int curLevel = 0;
        //当前节点个数统计
        int curNodeNum = 0;

        while(!queue.isEmpty()){
             head = queue.poll();
            if (levelMap.get(head) == curLevel) {
                curNodeNum ++;
            } else {
                max = Math.max(max, curNodeNum);
                curLevel ++;
                curNodeNum = 1;
            }
            if(head.left!= null) {
                levelMap.put(head.left, curLevel + 1);
                queue.add(head.left);
            }
            if(head.right!= null) {
                levelMap.put(head.right, curLevel + 1);
                queue.add(head.right);
            }
        }
        return Math.max(max, curNodeNum);
    }

搜索二叉树

所有子树左节点都比右小

判断是否为搜索二叉树

中序遍历 判断是否为依次升序、升序即为搜索二叉树

	public static boolean isBST(Tree head) {
		int preValue = 0;
		if(head == null) {
		reutrn true;
		}
		boolean result= isBST(head.left);
		if(!result){
			return false;
		}
		if(head.value <= preValue) {
			return false;
		}else{
			preValue = head.value;
		}
		return isBST(head.right);
	}

判断完全二叉树

1. 进行广度遍历并记录
2. 如果出现有右孩子无左孩子直接false
3. 满足2条件如果出现第一个左右不全必须为叶子节点