『LeetCode』#1刷题日记

class Solution {
    public int maxDepth(TreeNode root) {
        if(root == null) {
            return 0;   // 根节点为空 不存在 返回0
        } else {
            // 递归思路
            
            // root的左子树 根节点为root.left 右子树根节点为root.right
            // 找左右子树的层数最大值
            int left = maxDepth(root.left);
            int right = maxDepth(root.right);
            return Math.max(left, right) + 1;  
            // 最后一次 返回左子树和右子树中最深的层数+1 （1为根节点层数）
            // 在各个子树递归过程中，最后一层（left==null right==null 0+1=1）返回上一层、层层加一 
        }
    }
}
/**
 * Definition for a binary tree node.
 * 定义了一个二叉树的节点结构
 * public class TreeNode {
 *     int val;  当前节点值
 *     TreeNode left; 该节点的左孩子
 *     TreeNode right; 该节点的右孩子
 *     TreeNode() {} 
 *     TreeNode(int val) { this.val = val; } this方法 给节点赋值
 *     定义一个二叉树的方法
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */

class Solution {
    // 注意理解pre的含义 它始终指 当前访问的子树 的根节点的值 
    // 意在保证root.left.val < root.val
    long pre = Long.MIN_VALUE;
    public boolean isValidBST(TreeNode root) {

        if(root == null) {
            return true;
        }
        // 中序遍历 左中右的顺序
        // 左子树
        if(!isValidBST(root.left)) {    // 左子树不满足二叉搜索树的条件
            return false;
        }
        // 中 即当前节点
        if(root.val <= pre) {
            return false;
        }
        pre = root.val;

        // 访问右子树
        return isValidBST(root.right);
    }
}
/**
 * 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;
 *     }
 * }
 */

// 对于每一层 左子树根节点val == 右子树根节点val
// 同时 左子树的左孩子等于右子树的右孩子 左子树的右孩子等于右子树的左孩子
class Solution {
    public boolean isSymmetric(TreeNode root) {
        return dfs(root, root);
        // 理解 dfs(root, root) 类似于将树根看成一个镜像 树根的左孩子等于树根的右孩子 树根的右孩子等于树根的左孩子
    }

    public boolean dfs(TreeNode rootLeft, TreeNode rootRight) {
        if(rootLeft == null && rootRight == null) {
            return true;
        }

        if(rootLeft == null || rootRight == null || rootLeft.val != rootRight.val) {
            return false;
        } else {
            return dfs(rootLeft.left, rootRight.right) && dfs(rootLeft.right, rootRight.left);
        }
        
    }
}