222. 完全二叉树的节点个数

方法一：层序遍历

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public int countNodes(TreeNode root) {
        int count = 0;
        if(root == null) return 0;
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        while(!queue.isEmpty()){
            int n = queue.size();
            while(n > 0){
                TreeNode node = queue.poll();
                count++;
                if(node.left != null) queue.offer(node.left);
                if(node.right != null) queue.offer(node.right);
                n--;
            }
        } 
        return count;
    }
}

方法二：

递归解法：

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public int countNodes(TreeNode root) {
        if(root == null) {
            return 0;
        }
        return countNodes(root.left) + countNodes(root.right) + 1;
    }
}

110. 平衡二叉树

• 二叉树节点的深度：指从根节点到该节点的最长简单路径边的条数。

• 二叉树节点的高度：指从该节点到叶子节点的最长简单路径边的条数。

  既然要求比较高度，必然是要后序遍历。

  /**
   * Definition for a binary tree node.
   * public class TreeNode {
   *     int val;
   *     TreeNode left;
   *     TreeNode right;
   *     TreeNode() {}
   *     TreeNode(int val) { this.val = val; }
   *     TreeNode(int val, TreeNode left, TreeNode right) {
   *         this.val = val;
   *         this.left = left;
   *         this.right = right;
   *     }
   * }
   */
  class Solution {
      public boolean isBalanced(TreeNode root) {
          return getHeight(root) != -1;
      }
      public int getHeight(TreeNode root){
          if(root == null) return 0;
          int leftnode = getHeight(root.left);
          if(leftnode == -1) return -1;
          int rightnode = getHeight(root.right);
          if(rightnode == -1) return -1;
          if(Math.abs(leftnode - rightnode)>1){
              return -1;
          }else{
              return Math.max(leftnode,rightnode)+1;
          }
      }
  }
  
  
  

257. 二叉树的所有路径

夹杂着回溯的思想：

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public List<String> binaryTreePaths(TreeNode root) {
        List<String> list = new ArrayList<>();
        if(root == null) return list;
        List<Integer> path = new ArrayList<>();
        travel(root,list,path);
        return list;
    }

public void travel(TreeNode root,List<String> list,List<Integer> path){
    path.add(root.val);
    if(root.left == null && root.right == null){
        StringBuilder sb = new StringBuilder();
        //sb = path.get(0);
        sb.append(path.get(0));
        for(int i=1;i<path.size();i++){
            sb.append("->"+path.get(i));
        }
        String s = sb.toString();
        list.add(s);
        //return list;
        return;
    }
    if(root.left != null){
        travel(root.left,list,path);
        path.remove(path.size()-1); //回溯
    } 
    if(root.right != null){
        travel(root.right,list,path);
        path.remove(path.size()-1); //回溯
    }
    }   
}

100. 相同的树

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public boolean isSameTree(TreeNode p, TreeNode q) {
        return compare(p,q);
    }
    public boolean compare(TreeNode p,TreeNode q){
         // 排除了空节点，再排除数值不相同的情况
        if(p==null && q==null) return true;
        if(p==null || q==null) return false;
        if(p.val != q.val) return false;
        // 此时就是：左右节点都不为空，且数值相同的情况
        // 此时才做递归，做下一层的判断
        boolean b1 = compare(p.left,q.left);
        boolean b2 = compare(p.right,q.right);
        return b1&&b2;
    }
}

572. 另一棵树的子树

错因：对递归的过程理解不够，递归过程想不明白

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public boolean isSubtree(TreeNode s, TreeNode t) {
        if (t == null) return true;   // t 为 null 一定都是 true
        if (s == null) return false;  // 这里 t 一定不为 null, 只要 s 为 null，肯定是 false
        return isSubtree(s.left, t) || isSubtree(s.right, t) || isSameTree(s,t);
    }

    /**
     * 判断两棵树是否相同
     */
    public boolean isSameTree(TreeNode s, TreeNode t){
        if (s == null && t == null) return true;
        if (s == null || t == null) return false;
        if (s.val != t.val) return false;
        return isSameTree(s.left, t.left) && isSameTree(s.right, t.right);
    }
}