[数据结构与算法]Day9 二叉树-判断树类型（一）

一、二叉搜索树（BST - Binary Search Tree）

用中序遍历很容易实现，只要用中序遍历的过程是单调升序就代表是二叉搜索树

非递归：

//判断是否为二叉搜索树(binary search tree)
        //中序遍历
        static bool checkBST1(Node head)
        {
            if (head == null) return true;
            Stack<Node> stack = new Stack<Node>();
            int preValue = int.MinValue; 
            while (stack.Count > 0 || head!=null)
            {
                if(head != null)
                {
                    stack.Push(head);
                    head = head.left;
                }
                else
                {
                    head = stack.Pop();

                    if(head.value <= preValue)
                    {
                        return false;
                    }
                    else
                    {
                        preValue = head.value;
                    }
                    head = head.right;
                }
            }
            return true;
        }

递归遍历：

        static int preValue = int.MinValue;
        static bool checkBST2(Node head)
        {
            if (head == null) return true;
            bool isLeftBst = checkBST2(head.left);
            if (!isLeftBst)
            {
                return false;
            }
            if(head.value <= preValue)
            {
                return false;
            }
            else
            {
                preValue = head.value;
            }
            return checkBST2(head.right);
        }

二、完全二叉树（CBT - Complete Binary Tree）

用层次遍历一颗树时：只要这课树，有出现过节点存在空孩子，那么之后的节点必须是叶子节点。并且一个节点左孩子空而右孩子不空，那么一定不是完全二叉树。所以只要，拿一个bool开关记录是否出现过节点的孩子为空，之后遍历的时候判断节点是否有孩子便可。

代码：

        //判断是否为完全二叉树（complet binary tree）
        //层次遍历
        static bool checkCBT(Node head)
        {
            if(head ==null)
            {
                return false;
            }
            bool leaf = false;
            Node l = null;
            Node r = null;
            Queue<Node> queue = new Queue<Node>();
            queue.Enqueue(head);
            while (queue.Count > 0)
            {
                head = queue.Dequeue();
                l = head.left;
                r = head.right;
                if (
                        (leaf && ! (l == null && r == null ) )
                        ||
                        !(l == null && r != null)
                    )
                {
                    return false;
                }
                if(l != null)
                {
                    queue.Enqueue(l);
                }
                if(r != null)
                {
                    queue.Enqueue(r);
                }
                if(r == null || l == null) {
                    leaf = true;
                }
            }
            return true;
        }