文章目录

• 二叉树
• • 26. 二叉树的最近公共祖先
  • 28. 二叉搜索树的最近公共祖先
  • 29. 二叉搜索树中的插入操作

二叉树

26. 二叉树的最近公共祖先

236. 二叉树的最近公共祖先

思路：
后续遍历，如果找到目标节点，则返回目标节点，否则返回空。
每次回溯查看左右子树的返回值，如果有一个目标，则返回目标节点。
如果两个点都找到了，直接返回当前节点为最近公共祖先。

class Solution {
public:TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {if (root == nullptr || root == p || root == q) return root;TreeNode *left = lowestCommonAncestor(root->left, p, q);TreeNode *right =  lowestCommonAncestor(root->right, p, q);if (left && right) return root;if (left == nullptr) return right;return left;}
};

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

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

思路：
根据二叉搜索数的特性，两个节点的最近公共祖先的值一定在两节点之间（或者是某一个节点）。迭代法直接找即可。

class Solution {
public:TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {while (root) {if (root->val > p->val && root->val > q->val) root = root->left;else if (root->val < p->val && root->val < q->val) root = root->right;else return root;}return nullptr;}
};

29. 二叉搜索树中的插入操作

701. 二叉搜索树中的插入操作

方法1： 递归法
找到目标位置，通过递归返回值插入节点。

class Solution {
public:TreeNode* insertIntoBST(TreeNode* root, int val) {if (root == nullptr) {TreeNode *node = new TreeNode(val);return node;}if (root->val > val) root->left = insertIntoBST(root->left, val);if (root->val < val) root->right = insertIntoBST(root->right, val);return root;}
};

方法2：迭代法
需要目标位置，同时记录目标位置的父节点，方便插入节点。

class Solution {
public:TreeNode* insertIntoBST(TreeNode* root, int val) {if (root == nullptr) {TreeNode *node = new TreeNode(val);return node;}TreeNode *cur = root;TreeNode *parent = root;while (cur) {parent = cur;if (cur->val > val) cur = cur->left;else if (cur->val < val) cur = cur->right;}cur = new TreeNode(val);if (parent->val > val) parent->left = cur;else if (parent->val < val) parent->right = cur;return root;}
};