java实现二叉树常见操作

package com.xk.test.struct.newp;

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

public class MyBinaryTree {

    /**
     * 插入节点
     * @param root
     * @param node
     * @return
     */
    TreeNode insertNode(TreeNode root,TreeNode node){
        if(root == node){
            return node;
        }
        TreeNode tmp = new TreeNode();
        tmp = root;
        TreeNode last = null;
        while(tmp!=null){
            last = tmp;
            if(tmp.val>node.val){
                tmp = tmp.left;
            }else{
                tmp = tmp.right;
            }
        }
        if(last!=null){
            if(last.val>node.val){
                last.left = node;
            }else{
                last.right = node;
            }
        }
        return root;
    }
    
    /**
     * 递归解法前序遍历
     * @param root
     * @return
     */
    ArrayList preOrderReverse(TreeNode root){
        ArrayList result = new ArrayList();
        preOrder2(root,result);
        return result;
        
    }
    void preOrder2(TreeNode root,ArrayList result){
        if(root == null){
            return;
        }
        result.add(root.val);
        preOrder2(root.left,result);
        preOrder2(root.right,result);
    }
    
    /**
     * 迭代解法前序遍历
     * @param root
     * @return
     */
    ArrayList preOrder(TreeNode root){
        Stack stack = new Stack();
        ArrayList list = new ArrayList();
        if(root == null){
            return list;
        }
        stack.push(root);
        while(!stack.empty()){
            TreeNode node = stack.pop();
            list.add(node.val);
            if(node.right!=null){
                stack.push(node.right);
            }
            if(node.left != null){
                stack.push(node.left);
            }
            
        }
        return list;
    }
        
    /**
     * 中序遍历
     * @param root
     * @return
     */
    ArrayList inOrder(TreeNode root){
        ArrayList list = new ArrayList();
        Stack stack = new Stack();
        TreeNode current = root;
        while(current != null|| !stack.empty()){
            while(current != null){
                stack.add(current);
                current = current.left;
            }
            current = stack.peek();
            stack.pop();
            list.add(current.val);
            current = current.right;
            
        }
        return list;
    }
    
    /**
     * 后序遍历
     * @param root
     * @return
     */
    ArrayList postOrder(TreeNode root){
        ArrayList list = new ArrayList();
        if(root == null){
            return list;
        }
        list.addAll(postOrder(root.left));
        list.addAll(postOrder(root.right));
        list.add(root.val);
        return list;
    }
    
    /**
     * 最大深度
     * @param node
     * @return
     */
    int maxDeath(TreeNode node){
        if(node==null){
            return 0;
        }
        int left = maxDeath(node.left);
        int right = maxDeath(node.right);
        return Math.max(left,right) + 1;
    }
    
    /**
     * 层次遍历
     * @param root
     * @return
     */
    ArrayList> levelOrder(TreeNode root){
        ArrayList> result = new ArrayList>();
        if(root == null){
            return result;
        }
        Queue queue = new LinkedList();
        queue.offer(root);
        while(!queue.isEmpty()){
            int size = queue.size();
            ArrayList level = new ArrayList();
            for(int i = 0;i ){
                TreeNode node = queue.poll();
                level.add(node.val);
                if(node.left != null){
                    queue.offer(node.left);
                }
                if(node.right != null){
                    queue.offer(node.right);
                }
            } 
            result.add(level);
        }
        return result;
    }
    
    /**
     * 最小深度
     * @param root
     * @return
     */
    int getMinDepth(TreeNode root){
        if(root == null){
            return 0;
        }
        return getMin(root);
    }
    int getMin(TreeNode root){
        if(root == null){
            return Integer.MAX_VALUE;
        }
        if(root.left == null&&root.right == null){
            return 1;
        }
        return Math.min(getMin(root.left),getMin(root.right)) + 1;
    }
    
    /**
     * 节点的个数
     * @param root
     * @return
     */
    int numOfTreeNode(TreeNode root){
        if(root == null){
            return 0;
            
        }
        int left = numOfTreeNode(root.left);
        int right = numOfTreeNode(root.right);
        return left + right + 1;
    }
    
    /**
     * 叶子节点的个数
     * @param root
     * @return
     */
    int numsOfNodeTreeNode(TreeNode root){
        if(root == null){
            return 0;
        }
        if(root.left==null&&root.right==null){
            return 1;
        }
        return numsOfNodeTreeNode(root.left)+numsOfNodeTreeNode(root.right);
        
    }
    
    /**
     * 第k层节点的个数
     * @param root
     * @param k
     * @return
     */
    int numsOfkLevelTreeNode(TreeNode root,int k){
        if(root == null||k){
            return 0;
        }
        if(k==1){
            return 1;
        }
        int numsLeft = numsOfkLevelTreeNode(root.left,k-1);
        int numsRight = numsOfkLevelTreeNode(root.right,k-1);
        return numsLeft + numsRight;
    }
    
    /**
     * 翻转二叉树or镜像二叉树
     * @param root
     * @return
     */
    TreeNode mirrorTreeNode(TreeNode root){
        if(root == null){
            return null;
        }
        TreeNode left = mirrorTreeNode(root.left);
        TreeNode right = mirrorTreeNode(root.right);
        root.left = right;
        root.right = left;
        return root;
    }
    
    /**
     * 两个二叉树是否互为镜像
     * @param t1
     * @param t2
     * @return
     */
    boolean isMirror(TreeNode t1,TreeNode t2){
        if(t1==null&&t2==null){
            return true;
        }
        if(t1==null||t2==null){
            return false;
        }
        if(t1.val != t2.val){
            return false;
        }
        return isMirror(t1.left,t2.right)&&isMirror(t1.right,t2.left);
    }
    
    /**
     * 是否是平衡二叉树
     * 它是一棵空树或它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树。
     * @param node
     * @return
     */
    boolean isBalanced(TreeNode node){
        return maxDeath2(node)!=-1;
    }
    int maxDeath2(TreeNode node){
        if(node == null){
            return 0;
        }
        int left = maxDeath2(node.left);
        int right = maxDeath2(node.right);
        if(left==-1||right==-1||Math.abs(left-right)>1){
            return -1;
        }
        return Math.max(left, right) + 1;
    }
    
    /**
     * 是否是完全二叉树
     * 对于深度为K的，有n个结点的二叉树，当且仅当其每一个结点都与深度为K的满二叉树中编号从1至n的结点一一对应时称之为完全二叉树。
     * @param root
     * @return
     */
    boolean isCompleteTreeNode(TreeNode root){
        if(root == null){
            return false;
        }
        Queue queue = new LinkedList();
        queue.add(root);
        boolean result = true;
        boolean hasNoChild = false;
        while(!queue.isEmpty()){
            TreeNode current = queue.remove();
            if(hasNoChild){
                if(current.left!=null||current.right!=null){
                    result = false;
                    break;
                }
            }else{
                if(current.left!=null&&current.right!=null){
                    queue.add(current.left);
                    queue.add(current.right);
                }else if(current.left!=null&&current.right==null){
                    queue.add(current.left);
                    hasNoChild = true;
                    
                }else if(current.left==null&&current.right!=null){
                    result = false;
                    break;
                }else{
                    hasNoChild = true;
                }
            }
            
        }
        return result;
    }
    
    
    /**
     * 是否是合法的二叉查找树(BST)
    一棵BST定义为：
    节点的左子树中的值要严格小于该节点的值。
    节点的右子树中的值要严格大于该节点的值。
    左右子树也必须是二叉查找树。
    一个节点的树也是二叉查找树。
     */
    public int lastVal = Integer.MAX_VALUE;
    public boolean firstNode = true;
    public boolean isValidBST(TreeNode root) {
        // write your code here
        if(root==null){
            return true;
        }
        if(!isValidBST(root.left)){
            return false;
        }
        if(!firstNode&&lastVal >= root.val){
            return false;
        }
        firstNode = false;
        lastVal = root.val;
        if (!isValidBST(root.right)) {
            return false;
        }
        return true;
    }
    
    /**
     * 把二叉树打印成多行
     * @param pRoot
     * @return
     */
    ArrayList > Print(TreeNode pRoot) {
        ArrayList > res = new ArrayList >();
        if(pRoot == null)
            return res;
        ArrayList temp = new ArrayList();
        Queue layer = new LinkedList();
        layer.offer(pRoot);
        int start = 0, end = 1;
        while(!layer.isEmpty()){
            TreeNode node = layer.poll();
            temp.add(node.val);
            start ++;
            if(node.left != null)
                layer.add(node.left);
            if(node.right != null)
                layer.add(node.right);
            if(start == end){
                start = 0;
                res.add(temp);
                temp = new ArrayList();
                end = layer.size();
            }
        }
        return res;
    }
    
    /**
     * 按之字形顺序打印二叉树
     * @param pRoot
     * @return
     */
    public ArrayList > PrintZ(TreeNode pRoot) {
        ArrayList > res = new ArrayList >();
        Stack s1 = new Stack();
        Stack s2 = new Stack();
        int flag = 1;
        if(pRoot == null)
            return res;
        s2.push(pRoot);
        ArrayList temp = new ArrayList();
        while(!s1.isEmpty() || !s2.isEmpty()){
            if(flag % 2 != 0){
                while(!s2.isEmpty()){
                    TreeNode node = s2.pop();
                    temp.add(node.val);
                    if(node.left != null){
                        s1.push(node.left);
                    }
                    if(node.right != null){
                        s1.push(node.right);
                    }
                }
            }
            if(flag % 2 == 0){
                while(!s1.isEmpty()){
                    TreeNode node = s1.pop();
                    temp.add(node.val);
                    if(node.right != null){
                        s2.push(node.right);
                    }
                    if(node.left != null){
                        s2.push(node.left);
                    }
                }
            }
            res.add(new ArrayList(temp));
            temp.clear();
            flag ++;
        }
        return res;
    }

}

class TreeNode{
    int val;
    //左孩子
    TreeNode left;
    //右孩子
    TreeNode right;
}