101. 对称二叉树

题目

链接

代码

/**
 * 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 isSymmetric(TreeNode root) {
        if(root==null){
            return true;
        }   
        return traverse(root.left,root.right);
    }

    public boolean traverse(TreeNode left,TreeNode right){
        if(left==null&&right==null){
            return true;
        }
        if(left==null||right==null){
            return false;
        }
        if(left.val!=right.val){
            return false;
        }
        return traverse(left.left,right.right)&&traverse(left.right,right.left);
    }
}

104. 二叉树的最大深度

题目

链接

代码

/**
 * 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 maxDepth(TreeNode root) {
        findDepth(root,1);
        return maxDepth;
    }
    int maxDepth = 0;
    public void findDepth(TreeNode root,int depth){
        if(root==null){
            return;
        }
        maxDepth = Math.max(maxDepth,depth);
        findDepth(root.left,depth+1);
        findDepth(root.right,depth+1);
    }
}

111. 二叉树的最小深度

题目

链接

代码

/**
 * 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 minDepth(TreeNode root) {
        if(root==null){
            return 0;
        }
        traverse(root,1);
        return min;
    }   
    int min = Integer.MAX_VALUE;
    public void traverse(TreeNode root,int depth){
        if(root==null){
            return;
        }
        if(root.left==null&&root.right==null){
            min = Math.min(min,depth);
        }
        traverse(root.left,depth+1);
        traverse(root.right,depth+1);
    }
}

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) {
        preOrder(root);
        return count;
    }

    int count = 0;
    public void preOrder(TreeNode root){
        if(root==null){
            return;
        }
        count++;
        preOrder(root.left);
        preOrder(root.right);
    }
}

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) {
        if(root==null){
            return true;
        }
        high(root);
        return isBalanced;
    }
    boolean isBalanced = true;
    public int high(TreeNode root){
        if(root==null){
            return 0;
        }
        if(root.left==null&&root.right==null){//叶子高为1
            return 1;
        }

        int left = high(root.left);
        int right = high(root.right);
        if(Math.abs(left-right)>1){
            isBalanced = false;
        }

        return Math.max(left,right)+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) {
        preOrder(root);
        return result;
    }

    List<String> result = new ArrayList();
    List<Integer> list = new ArrayList();
    public void preOrder(TreeNode root){
        if(root==null){
            return;
        }
        list.add(root.val);
        if(root.left==null&&root.right==null){
            StringBuilder sb = new StringBuilder();
            for(int i =0;i<list.size();i++){
                if(i==0){
                    sb.append(list.get(i));
                }else{
                    sb.append("->"+list.get(i));
                }
            }
            result.add(sb.toString());
        }

        if(root.left!=null){
            preOrder(root.left);
            list.remove(list.size()-1);
        }
        if(root.right!=null){
            preOrder(root.right);
            list.remove(list.size()-1);
        }
        
    }
}