第一行输入两个整数 n 和 root,n 表示二叉树的总节点个数,root 表示二叉树的根节点。
以下 n 行每行三个整数 fa,lch,rch,表示 fa 的左儿子为 lch,右儿子为 rch。(如果 lch 为 0 则表示 fa 没有左儿子,rch同理)
ps:节点的标号就是节点的值
第一行输出该二叉树是否为搜索二叉树的答案,如果是则输出 "true",否则输出 "false"。
第二行输出该二叉树是否为完全二叉树的答案,如果是则输出 "true",否则输出 "false"。
3 2 2 1 3 1 0 0 3 0 0
true true
import java.io.BufferedReader; import java.io.InputStreamReader; import java.io.IOException; import java.util.HashMap; import java.util.Stack; import java.util.LinkedList; import java.util.Queue; class TreeNode { public int val; public TreeNode left; public TreeNode right; public TreeNode(int val) { this.val = val; } } public class Main { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); // 构建二叉树 String[] params = br.readLine().split(" "); int n = Integer.parseInt(params[0]); TreeNode root = new TreeNode(Integer.parseInt(params[1])); HashMap<Integer, TreeNode> map = new HashMap<>(); map.put(root.val, root); for(int i = 0; i < n; i++){ params = br.readLine().split(" "); int val = Integer.parseInt(params[0]); int leftVal = Integer.parseInt(params[1]); int rightVal = Integer.parseInt(params[2]); TreeNode node = map.get(val); if(leftVal != 0) { node.left = new TreeNode(leftVal); map.put(leftVal, node.left); } if(rightVal != 0) { node.right = new TreeNode(rightVal); map.put(rightVal, node.right); } } // 判断二叉搜索树 System.out.println(isBST(root)); // 判断完全二叉树 System.out.println(isCBT(root)); } private static boolean isBST(TreeNode root) { int prev = Integer.MIN_VALUE; Stack<TreeNode> stack = new Stack<>(); while(!stack.isEmpty() || root != null){ while(root != null){ stack.push(root); root = root.left; } if(!stack.isEmpty()){ root = stack.pop(); if(root.val <= prev) return false; // 破坏了中序遍历的单调递增特性,直接返回false else prev = root.val; root = root.right; } } return true; } private static boolean isCBT(TreeNode root) { Queue<TreeNode> queue = new LinkedList<>(); queue.offer(root); boolean flag = false; // 孩子不双全的节点是否出现过 while(!queue.isEmpty()){ TreeNode node = queue.poll(); if(node.left == null && node.right != null) return false; // 有右孩子没有左孩子 if((node.left != null || node.right != null) && flag) return false; // 出现过左右孩子不双全的节点,之后必须全部是叶子节点 if(node.left == null || node.right == null) flag = true; // 遇到左右孩子不双全的节点 if(node.left != null) queue.offer(node.left); if(node.right != null) queue.offer(node.right); } return true; } }
class TreeNode { int val; TreeNode left; TreeNode right; TreeNode(int val) { this.val = val; } } /* private static TreeNode buildTree(Scanner sc, int n, int rootVal) { Map<Integer, TreeNode> map = new HashMap<>(); while (n-- > 0) { int fa = sc.nextInt(); int lch = sc.nextInt(); int rch = sc.nextInt(); TreeNode faNode = map.get(fa); if (faNode == null) { faNode = new TreeNode(fa); map.put(fa, faNode); } if (lch != 0) { TreeNode lchNode = map.get(lch); if (lchNode == null) { lchNode = new TreeNode(lch); map.put(lch, lchNode); } faNode.left = lchNode; } if (rch != 0) { TreeNode rchNode = map.get(rch); if (rchNode == null) { rchNode = new TreeNode(rch); map.put(rch, rchNode); } faNode.right = rchNode; } } return map.get(rootVal); } */
import java.util.*; public class Main { public static void main(String[] args) { Scanner sc = new Scanner(System.in); int n = sc.nextInt(); int rootVal = sc.nextInt(); TreeNode root = buildTree(sc, n, rootVal); System.out.println(isBST(root, new int[]{Integer.MIN_VALUE})); System.out.println(isCompleteBinaryTree(root)); } private static boolean isCompleteBinaryTree(TreeNode root) { if (root == null) { return true; } Queue<TreeNode> que = new LinkedList<>(); que.add(root); while(!que.isEmpty()) { int sz = que.size(); for (int i = 0; i < sz; ++i) { TreeNode node = que.poll(); if (node.left != null && node.right != null) { que.add(node.left); que.add(node.right); } else { if (node.left == null && node.right != null) { return false; } if (node.left != null) { que.add(node.left); } while(!que.isEmpty()) { TreeNode vnode = que.poll(); if (vnode.left != null || vnode.right != null) { return false; } } break; } } } return true; } private static boolean isBST(TreeNode root, int[] pre) { if (root == null) { return true; } if (!isBST(root.left, pre)) { return false; } if (pre[0] > root.val) { return false; } pre[0] = root.val; return isBST(root.right, pre); } private static TreeNode buildTree(Scanner sc, int n, int rootVal) { Map<Integer, TreeNode> map = new HashMap<>(); while (n-- > 0) { int fa = sc.nextInt(); int lch = sc.nextInt(); int rch = sc.nextInt(); TreeNode faNode = map.get(fa); if (faNode == null) { faNode = new TreeNode(fa); map.put(fa, faNode); } if (lch != 0) { TreeNode lchNode = map.get(lch); if (lchNode == null) { lchNode = new TreeNode(lch); map.put(lch, lchNode); } faNode.left = lchNode; } if (rch != 0) { TreeNode rchNode = map.get(rch); if (rchNode == null) { rchNode = new TreeNode(rch); map.put(rch, rchNode); } faNode.right = rchNode; } } return map.get(rootVal); } }
import java.util.*; class node { int val; node left, right; node(int val) { this.val = val; } } public class Main { private static int pre = 0; public static void main(String[] args) { Scanner scanner = new Scanner(System.in); int n = scanner.nextInt(); node root = new node(scanner.nextInt()); HashMap<Integer, node> map = new HashMap<>(); map.put(root.val, root); for(int i=0;i<n;i++) { node parent, left, right; parent = getNodeIfExist(map, scanner.nextInt()); left = getNodeIfExist(map, scanner.nextInt()); right = getNodeIfExist(map, scanner.nextInt()); parent.left = left; parent.right = right; } System.out.println(isBST(root)); System.out.println(isCBT(root)); } private static boolean isBST(node root) { //是否二叉搜索树 if(root == null) return true; boolean left = isBST(root.left); if(left) { if(pre > root.val) return false; pre = root.val; } return left && isBST(root.right); } private static boolean isCBT(node root) { //是否完全二叉树 if(root == null) return true; Queue<node> queue = new LinkedList<>(); queue.add(root); boolean leaf = false; while(queue.size() != 0) { node head = queue.remove(); if(head.right != null && head.left == null) return false; if(head.left != null && head.right == null) { if(leaf) return false; leaf = true; } if(head.left != null) { queue.add(head.left); } if (head.right != null) { queue.add(head.right); } } return true; } private static node getNodeIfExist(HashMap<Integer, node> map, int val) { if(val == 0) return null; if(map.get(val) == null) { map.put(val, new node(val)); } return map.get(val); } }