二叉树的相关概念和解题套路

判断一棵二叉树是否是搜索二叉树:

解 : 中序遍历 然后遍历之后 的顺序是升序的 就是平衡二叉树;
在遍历过程中把打印行为 换成 和前一个节点比较大小的行为;

判断二叉树是否是完全二叉树:

解:

1. 在宽度搜索过程中 任意一节点有右无左就不是
   2.第一个节点左右不双全 则剩下的所有都是 叶节点;

package tree;

import java.util.LinkedList;

public class wanquantree {
    public static class Node {
        public int value;
        public Node left;
        public Node right;

        public Node(int data) {
            this.value = data;
        }
    }


    //二叉树的宽度优先遍历
    static boolean width(Node root) {
        if (root == null) {
            return false;
        }
        LinkedList<Node> queue = new LinkedList<Node>();
        queue.add(root);
        boolean isleaf = false;
        while (!queue.isEmpty()) {
            Node node = queue.poll();
            Node l = node.left;
            Node r = node.right;
            System.out.print(node.value);
            if ((l == null && r != null)       //左边为空 右边不为空
                    ||
                    (isleaf && (l != null || r != null))      //是叶节点了 并且 还有节点有孩子
            ) {
                return false;
            }
            if (node.left != null) {
                queue.add(node.left);
            }
            if (node.right != null) {
                queue.add(node.right);
            }
            if (l == null || r == null) {//在遍历过程中是否到了叶节点
                isleaf = true;
            }
        }
        return true;
    }

    public static void main(String[] args) {
        Node node = new Node(1);
        Node node2 = new Node(2);
        Node node3 = new Node(3);
        Node node4 = new Node(4);

        node.left = node2;
        node.right = node3;
        node2.left = node4;

        boolean width = width(node);
        System.out.println();
        System.out.println(width);
    }


}

判断树是不是平衡二叉树

package tree;

public class banlance {
    public static class Node {
        public int value;
        public Node left;
        public Node right;

        public Node(int data) {
            this.value = data;
        }
    }

    public static boolean isBalanced(Node head) {
        return process(head,0).isBalanced;
    }

    public static class ReturnType {//封装返回信息
        public boolean isBalanced;
        public int height;

        public ReturnType(boolean isB, int hei) {
            isBalanced = isB;
            height = hei;
        }

    }

    public static ReturnType process(Node x,int height) {
        if (x == null) {
            return new ReturnType(true, height);//返回true 和得到的高度
        }
        ReturnType leftData = process(x.left,height+1);
        ReturnType rightData = process(x.right,height+1);
        height = Math.max(leftData.height, rightData.height);//黑盒 左右的最大高度
        boolean isBalanced = leftData.isBalanced && rightData.isBalanced
                && Math.abs(leftData.height - rightData.height) < 2;// 左右是平衡 并且 左右高度 相差小于2
        return new ReturnType(isBalanced, height);
    }

    public static void main(String[] args) {
        Node node = new Node(1);
        Node node2 = new Node(2);
        Node node3= new Node(3);
//        Node node4= new Node(4);
//        Node node5= new Node(5);

        node.left=node2;
        node.right=node3;
//        node3.left=node4;
//        node4.right=node5;
        ReturnType process = process(node,0);
        System.out.println(process.isBalanced+""+process.height);
//        System.out.println(isBalanced(node));

    }

}

用returntype封装信息 按照总能向左右子树要信息 并组装返回