题解 | Java #判断一棵二叉树是否为搜索二叉树和完全二叉树# [P0-T2]

搜索二叉树:
in-order traversal (iterative). 记录上一次visit的值 (lastPoped)。没次visit只要check值是不是小于lastPoped.
相同解法也可以用recursion实现，但是需要把lastPoped存成global。

完全二叉树:
level-order traversal (iterative). 层序遍历中第一次看到null就让ended=true，表示所有非null的node都遍历完了。 那么之如果再见到非null的node那么tree就不是complete。

import java.util.*;

public class Solution {
    public boolean[] judgeIt (TreeNode root) {
      return new boolean[]{ isBST(root), isComplete(root) };
    }
  
    public boolean isBST(TreeNode root) {
      if (root == null) return true;
      
      Deque<TreeNode> stack = new ArrayDeque<>();
      TreeNode next = root;
      int lastPoped = -1;
      
      while (!stack.isEmpty() || next != null) {
        if (next != null) {
          stack.push(next);
          next = next.left;
        } else {
          TreeNode pop = stack.pop();
          if (pop.val < lastPoped) {
            return false;
          } else {
            lastPoped = pop.val;
            next = pop.right;
          }
        }
      }
      return true;
    }
  
    public boolean isComplete(TreeNode root) {
      if (root == null) return true;
      
      Queue<TreeNode> q = new LinkedList<>();
      q.offer(root);
      boolean ended = false;
      while (!q.isEmpty()) {
        TreeNode head = q.poll();
        if (head == null) {
          ended = true;  // 看到null就表示Queue里剩下的必须全是null
        } else {
          if (ended) return false;  // ended but null，不是complete tree
          q.offer(head.left);
          q.offer(head.right);
        }
      }
      return true;
    }
}