网站开发简历 自我评价,进入江苏省住房和城乡建设厅网站首页,wordpress ios shared,迅腾网络网站建设有限公司二叉树的最近公共祖先 思路
在左、右子树中分别查找是否包含p或q#xff1a;如果以下两种情况#xff08;左子树包含p#xff0c;右子树包含q/左子树包含q#xff0c;右子树包含p#xff09;#xff0c;那么此时的根节点就是最近公共祖先如果左子树包含p和q#xff0c;…二叉树的最近公共祖先 思路
在左、右子树中分别查找是否包含p或q如果以下两种情况左子树包含p右子树包含q/左子树包含q右子树包含p那么此时的根节点就是最近公共祖先如果左子树包含p和q那么到root-left中继续查找最近公共祖先在左子树里面如果右子树包含p和q那么到root-right中继续查找最近公共祖先在右子树里面 struct TreeNode {int val;TreeNode *left;TreeNode *right;TreeNode(int x) : val(x), left(NULL), right(NULL) {}};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);return left nullptr ? right : (right nullptr ? left : root);}
};二叉树搜索树转换成排序双向链表 二叉搜索树普通的二叉树
左子树所有结点小于根右子树所有结点大于根中序有序
Node *prev NULL;
void func(Node *node){node-left prev; //等于上面的node-prev;if(prev ! NULL){prev-right node ; //等于上面的prev-next}prev node;
}void inorder(Node *root){if(root NULL)return ;inorder(root-left);func(root);inorder(root-right);
}class Solution {
public:TreeNode *prev NULL;TreeNode *first ;void fun(TreeNode * node){node-left prev;if(prev!NULL){prev-right node;}else{first node;}prev node;}void Inorder(TreeNode *root){if(root NULL){return ;}Inorder(root-left);fun(root);Inorder(root-right);}TreeNode* Convert(TreeNode* pRootOfTree){first NULL;Inorder(pRootOfTree);return first;}
};
