104. 二叉樹的最大深度

描述

• 給定一個(gè)二叉樹例嘱，找出其最大深度狡逢。
• 二叉樹的深度為根節(jié)點(diǎn)到最遠(yuǎn)葉子節(jié)點(diǎn)的最長(zhǎng)路徑上的節(jié)點(diǎn)數(shù)。

說明

• 葉子節(jié)點(diǎn)是指沒有子節(jié)點(diǎn)的節(jié)點(diǎn)拼卵。

示例

  給定二叉樹 [3,9,20,null,null,15,7]奢浑，

    3
   / \
  9  20
    /  \
   15   7
  返回它的最大深度 3 。

思路

1. 利用遞歸深度遍歷二叉樹腋腮，一個(gè)樹的最大深度等于左右子樹最大深度+1

struct TreeNode {
  int val;
  TreeNode* left;
  TreeNode* right;
  TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};
class Solution_104 {
 public:
  int maxDepth(TreeNode* root) {
    if (root == NULL) return 0;
    int leftDepth = maxDepth(root->left);
    int rightDepth = maxDepth(root->right);
    return leftDepth > rightDepth ? leftDepth + 1 : rightDepth + 1;
  }
};

98. 驗(yàn)證二叉搜索樹

描述

• 給定一個(gè)二叉樹雀彼，判斷其是否是一個(gè)有效的二叉搜索樹壤蚜。

示例

  一個(gè)二叉搜索樹具有如下特征：
    節(jié)點(diǎn)的左子樹只包含小于當(dāng)前節(jié)點(diǎn)的數(shù)。
    節(jié)點(diǎn)的右子樹只包含大于當(dāng)前節(jié)點(diǎn)的數(shù)徊哑。
    所有左子樹和右子樹自身必須也是二叉搜索樹袜刷。
  
  示例 1:
  輸入:
      2
    / \
    1   3
  輸出: true

  示例 2:
  輸入:
      5
    / \
    1   4
      / \
      3   6
  輸出: false
  解釋: 輸入為: [5,1,4,null,null,3,6]。根節(jié)點(diǎn)的值為 5 莺丑，但是其右子節(jié)點(diǎn)值為 4 著蟹。

思路

1. 利用搜索樹的特性來驗(yàn)證，即左<根<右窒盐。左邊所有的節(jié)點(diǎn)都比根節(jié)點(diǎn)小草则，右邊所有的節(jié)點(diǎn)都比根節(jié)點(diǎn)大。所以每次遞歸傳入一個(gè)最小值蟹漓、一個(gè)最大值炕横，所有節(jié)點(diǎn)都需滿足規(guī)則。
2. 題目說明是小于和大于葡粒，沒有相等的情況份殿，因此可以利用中序遍歷序列為有序序列來驗(yàn)證。

Tips

1. 第一次嘗試的解法是錯(cuò)誤的嗽交，認(rèn)為只要左節(jié)點(diǎn)小于根節(jié)點(diǎn)卿嘲，右節(jié)點(diǎn)大于根節(jié)點(diǎn)就滿足要求。忽略了整個(gè)左子樹中每個(gè)點(diǎn)都要比根小夫壁，整個(gè)右子樹中每個(gè)點(diǎn)都比根要大的特性拾枣。
2. 參考了網(wǎng)上的一個(gè)博文(地址)

class Solution_98_01 {
 public:
  bool isValidBST(TreeNode* root) {
    return _isValidBST(root, LONG_MIN, LONG_MAX);
  }
  bool _isValidBST(TreeNode* root, long min, long max) {
    if (root == NULL) return true;
    if (root->val <= min || root->val >= max) return false;
    return _isValidBST(root->left, min, root->val) &&
           _isValidBST(root->right, root->val, max);
  }
};

class Solution_98_02 {
 public:
  bool isValidBST(TreeNode* root) {
    if (root == NULL)
      return true;  // 此行注釋掉會(huì)報(bào)錯(cuò)，reference binding to null pointer of
                    // type 'value_type'
    vector<int> nums;
    inOrder(root, nums);
    for (int i = 0; i < nums.size() - 1; ++i) {
      if (nums[i] >= nums[i + 1]) return false;
    }
    return true;
  }
  void inOrder(TreeNode* root, vector<int>& nums) {
    if (root == NULL) return;
    inOrder(root->left, nums);
    nums.push_back(root->val);
    inOrder(root->right, nums);
  }
};