leetcode树

简单

100 相同的树

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    bool isSameTree(TreeNode* p, TreeNode* q) {
        //如果p和q都为NULL，那么返回true
        if(!p && !q) return true;
		// p有一个是NULL，一个非空，那么返回false
        if(!p || !q) return false;
        //同时满足 p->val == q->val 左子树右子树都相等，才返回true
        return (p->val == q->val) 
                && (isSameTree(p->left,q->left) 
                && isSameTree(p->right,q->right));
    }
};

101 对称二叉树

104 二叉树的最大深度

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
       int maxDepth(TreeNode* root) {
        if(root == NULL) return 0;
        int left = maxDepth(root->left);
        int right = maxDepth(root->right);
        return max(left, right) + 1;
    }
};

面试4.04 检查平衡性

题解

定义一个bool值，然后在深度搜索的时候时刻判断左右子树的高度差是否超过了1

当左右节点等于null的时候，就返回0 ；当左右子树不相等的时候，返回左右子树最大深度加一作为当前节点的深度。

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
    bool ans = true;
    int maxDepth(TreeNode* root) {
        if(root == NULL) return 0;
        int left = maxDepth(root->left);
        int right = maxDepth(root->right);
        if(abs(left - right) > 1) 
            ans = false;
        return max(left, right) + 1;
    }
public:
    bool isBalanced(TreeNode* root) {
        if(root == NULL) return true;
        maxDepth(root);
        return ans;
    }
};

中等