두 갈래 나무가 완전한 두 갈래 나무인지 아닌지를 판단하는 실례

완전 두 갈래 나무 특징
완전 두 갈래 나무는 마지막 층을 제외한 모든 층의 결점수가 가득 찬 것을 가리킨다.마지막 층도 가득 차면 두 갈래 나무이자 완전 두 갈래 나무다.마지막 층이 불만족스러우면 부족한 결점도 모두 왼쪽에 집중된다. 그것도 완전히 두 갈래 나무다.
두 갈래 나무가 완전한 두 갈래 나무인지 아닌지를 판단하다

import java.util.*;
class TreeNode {
  int val = 0;
  TreeNode left = null;
  TreeNode right = null;
  public TreeNode(int val) {
    this.val = val;
  }
}
public class CheckCompletion {
  public boolean checking(TreeNode root) {
    Queue<TreeNode> queue = new LinkedList<TreeNode>();
    boolean leaf = false; //  
    TreeNode left;
    TreeNode right;
    queue.add(root);
    while (!queue.isEmpty()) {
      root = queue.poll();
      left = root.left;
      right = root.right;
      if ((leaf&&(left!=null||right!=null)) || (left==null&&right!=null)) {
        //  , , false
        //  , false
        return false;
      }
      if (left != null) {
        queue.offer(root.left);
      }
      if (right != null) {
        queue.offer(root.right);
      }else {
        leaf = false; //  , 
      }
    }
    return true;
  }
}

읽어주셔서 감사합니다. 여러분에게 도움이 되었으면 좋겠습니다. 본 사이트에 대한 지지에 감사드립니다!

좋은 웹페이지 즐겨찾기