leetcode-hot-100-20230928

101. 对称二叉树（Java递归实现）

/**
 * 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 duichen(TreeNode left, TreeNode right){
        //首先判断特殊情况
        if(left == null && right != null){
            return false;
        }else if(left != null && right == null){
            return false;
        }else if(left == null && right == null){
            return true;
        }else if(left.val != right.val){
            return false;
        }

        //递归调用
        //外部结点：左子树的左结点，右子树的右结点
        boolean outside = duichen(left.left, right.right);
        //内部结点，左子树的右结点，右子树的左结点
        boolean inside = duichen(left.right, right.left);

        boolean eq = outside && inside;

        return eq;
    }


    public boolean isSymmetric(TreeNode root) {
        if(root == null){
            return true;
        }

        return duichen(root.left, root.right);
    }
}

101. 对称二叉树（Java使用单个队列实现）

/**
 * 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;
        }

        //创建对立
        Queue<TreeNode> que = new LinkedList<>();
        //添加首部结点
        que.offer(root.left);
        que.offer(root.right);

        //循环判断进入条件，两个队列不是空
        while(!que.isEmpty()){
            //获得两个队列中的结点
            TreeNode left = que.peek();
            //弹出头部结点
            que.poll();
            TreeNode right = que.peek();
            que.poll();

            //判断两个结点
            if(left == null && right == null){
                continue;
            }else if(left == null && right != null){
                return false;
            }else if(left != null && right == null){
                return false;
            }else if(left.val != right.val){
                return false;
            }

            //添加新的队列结点
            que.offer(left.left);
            que.offer(right.right);

            //添加内侧结点
            que.offer(left.right);
            que.offer(right.left);
        }

        return true;
    }
}

543. 二叉树的直径（Java实现）

/**
 * 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 {

    int result = 0;

    public int digui(TreeNode root){
        //思路：左边到最深处的叶子结点，右边到最深处的叶子结点
        if(root == null){
            return 0;
        }

        int leftDepth = digui(root.left);
        int rightDepth = digui(root.right);

        result = Math.max(result, leftDepth + rightDepth + 1);
        return Math.max(leftDepth, rightDepth) + 1;
    }

    public int diameterOfBinaryTree(TreeNode root) {
        result = 1;

        digui(root);

        return result - 1;
    }
}