title: 【每日一题】LeetCode 783.二叉搜索树节点最小距离
tags:

  • leetcode
  • acwing
  • 树
    abbrlink: dbf62d11
    date: 2021-04-13 12:14:46

LeetCode 783.二叉搜索树节点最小距离

思路

今天的题都比较无脑，直接无脑dfs搜索最小差值，暴力搜索一遍得出的最后结果就是最小值

C++代码

  1. /**
  2.  * Definition for a binary tree node.
  3.  * struct TreeNode {
  4.  *     int val;
  5.  *     TreeNode *left;
  6.  *     TreeNode *right;
  7.  *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
  8.  *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
  9.  *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
  10.  * };
  11.  */
  12. class Solution {
  13. public:
  14.     int ans, last;
  15.     bool is_first;
  16.     int minDiffInBST(TreeNode* root) {
  17.         ans=INT_MAX, is_first=true;
  18.         dfs(root);
  19.         return ans;
  20.     }
  22.     void dfs(TreeNode* root)
  23.     {
  24.         if(!root)   return;
  25.         dfs(root->left);
  26.         if(is_first)
  27.         {
  28.             last=root->val;
  29.             is_first=false;
  30.         }
  31.         else
  32.         {
  33.             ans=min(ans, root->val-last);
  34.             last=root->val;
  35.         }
  36.         dfs(root->right);
  37.     }
  38. };

AcWing 71.二叉树的深度

思路

无脑递归

C++代码

  1. /**
  2.  * Definition for a binary tree node.
  3.  * struct TreeNode {
  4.  *     int val;
  5.  *     TreeNode *left;
  6.  *     TreeNode *right;
  7.  *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
  8.  * };
  9.  */
  10. class Solution {
  11. public:
  12.     int treeDepth(TreeNode* root) {
  13.         if(!root)   return 0;
  14.         return max(treeDepth(root->left), treeDepth(root->right))+1;
  15.     }
  16. };