二叉树：每个节点最多有两个子树，这两个子树有左右之分，次序不可颠倒。

前序遍历：先访问自己，再访问左子树，最后右子树
中序遍历：先访问左子树，再访问自己，最后右子树
后序遍历：先访问左子树，再访问右子树，最后自己

图：1.深搜 2.广搜 

  1. struct TreeNode
  2. {
  3.     int val;
  4.     TreeNode *left;
  5.     TreeNode *right;
  6.     TreeNode(int x) : val(x), left(NULL), right(NULL){}
  7. }

1、验证二叉搜索树(medium)

  • 递归解决，进行左子树搜索时，有上界，进行右子树解决时，有下界
    1. class Solution {
    2. public:
    3.   bool helper(TreeNode* root, long long lower, long long upper) {
    4.       if (root == nullptr) return true;
    5.       if (root -> val <= lower || root -> val >= upper) return false;
    6.       return helper(root -> left, lower, root -> val) && helper(root -> right, root -> val, upper);
    7.   }
    8.   bool isValidBST(TreeNode* root) {
    9.       return helper(root, LONG_MIN, LONG_MAX);
    10.   }
    11. };

235. 二叉搜索树最近的公共祖先

从根节点开始遍历树

  1. 如果节点 p 和节点 q 都在右子树上，那么以右子树为根节点继续 1 的操作
  2. 如果节点 p 和节点 q 都在左子树上，那么以左子树为根节点继续 1 的操作
  3. 如果条件 2 和条件 3 都不成立，这就意味着我们已经找到节 p 和节点 q 的 LCA 了
    1. class Solution {
    2. public:
    3.  TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
    4.      int parentval = root->val;
    5.      int pval =p->val;
    6.      int qval =q->val;
    7.      if(pval>parentval&&qval>parentval)
    8.      {
    9.          return lowestCommonAncestor(root->right,p,q);
    10.      }
    11.      else if(pval<parentval&&qval<parentval)
    12.      {
    13.          return lowestCommonAncestor(root->left,p,q);
    14.      }
    15.      else
    16.      {
    17.          return root;
    18.      }
    19.  }
    20. };

    更多算法题训练：

  • 路径之和，求所有从跟节点到叶节点路径之和为sum的组合 —->113(Medium)
  • 最近的公共祖先，给两个节点，求公共祖先，越深越好 —->236(Medium)
  • 二叉树转链表，给定一个二叉树，原地将它展开为链表。 —->114(Medium)
  • 二叉树的右视图。返回右侧能看到的节点值 —->199(Medium)
  • 课程安排。有依赖关系 —->207(Medium)