// 给定一棵二叉树, 找到该树中两个指定节点的最近公共祖先
// 思路：从根节点开始遍历，如果node1和node2中的任一个和root匹配，那么root就
// 是最低公共祖先。 如果都不匹配，则分别递归左、右子树，如果有一个
// 节点出现在左子树，并且另一个节点出现在右子树，则root就是最低公共祖先.
// 如果两个节点都出现在左子树，则说明最低公共祖先在左子树中，否则在右子树。
public class Solution {
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
//发现目标节点则通过返回值标记该子树发现了某个目标结点
if(root == null || root == p || root == q) return root;
//查看左子树中是否有目标结点，没有为null
TreeNode left = lowestCommonAncestor(root.left, p, q);
//查看右子树是否有目标节点，没有为null
TreeNode right = lowestCommonAncestor(root.right, p, q);
//都不为空，说明做右子树都有目标结点，则公共祖先就是本身
if(left!=null&&right!=null) return root;
//如果发现了目标节点，则继续向上标记为该目标节点
return left == null ? right : left;
}
}
void k(int i,int j)
{
while(true)
{
if(i==j)
{
break;
}
if(i>j)
{
i/=2;
}
else
{
j/=2;
}
}
printf("%d\n",i);
}
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
vector<string> binaryTreePaths(TreeNode* root) {
vector<string> res;
if(root==nullptr)
return res;
string temp;
binary(root, temp, res);
return res;
}
void binary(TreeNode* root, string temp, vector<string> &res )
{
if(!root->left && !root->right)
res.push_back(temp+to_string(root->val));
if(root->left)
{
binary(root->left, temp+to_string(root->val)+"->",res);
}
if(root->right)
{
binary(root->right, temp+to_string(root->val)+"->",res);
}
}
};
// 如果一个节点是叶子节点，则不做操作；如果一个节点只有左孩子或者右孩子，则
// 进行交换，原来的孩子为空；如果一个节点既有左孩子和右孩子，则交换左右孩子
// 交换左右子树
void ReverseLeftRightChild(BiTNode **T)
{
// 如果是叶子节点，则递归结束
if (*T == NULL)
{
return;
}
swap((*T)->lChild, (*T)->rChild); // 直接使用swap交换函数比较方便，直接交换指针；
ReverseLeftRightChild(&((*T)->lChild));
ReverseLeftRightChild(&((*T)->rChild));
}
/**
* Definition for binary tree
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
int minDepth(TreeNode *root) {
if (root == NULL) return 0;
if (root->left == NULL && root->right == NULL) return 1;
if (root->left == NULL) return minDepth(root->right) + 1;
else if (root->right == NULL) return minDepth(root->left) + 1;
else return 1 + min(minDepth(root->left), minDepth(root->right));
}
};
/**
* Definition of TreeNode:
* class TreeNode {
* public:
* int val;
* TreeNode *left, *right;
* TreeNode(int val) {
* this->val = val;
* this->left = this->right = NULL;
* }
* }
*/
class Solution {
public:
/**
* @param root: The root of binary tree.
* @return: An integer
*/
int maxDepth(TreeNode *root) {
if(root==NULL){
return NULL;
}
int left=maxDepth(root->left);
int right=maxDepth(root->right);
return (left>right)?(left+1):(right+1);
}
};
// 使用队列，层次遍历二叉树。在上一层遍历完成后，下一层的所有节点已经放到队
// 列中，此时队列中的元素个数就是下一层的宽度。以此类推，依次遍历下一层即可
// 求出二叉树的最大宽度
public static int getMaxWidth(TreeNode root) {
if (root == null)
return 0;
Queue<TreeNode> queue = new ArrayDeque<TreeNode>();
int maxWitdth = 1; // 最大宽度
queue.add(root); // 入队
while (true) {
int len = queue.size(); // 当前层的节点个数
if (len == 0)
break;
while (len > 0) {// 如果当前层，还有节点
TreeNode t = queue.poll();
len--;
if (t.left != null)
queue.add(t.left); // 下一层节点入队
if (t.right != null)
queue.add(t.right);// 下一层节点入队
}
maxWitdth = Math.max(maxWitdth, queue.size());
}
return maxWitdth;
}
// 左右子树的深度差的绝对值不大于1
// 左子树和右子树也都是平衡二叉树
// 所以我们只需要在求一棵树的深度的代码中加上高度差判断就可以
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
int judge(TreeNode* root,bool &ans)
{
if(root)
{
int ans1 = judge(root->left,ans);
int ans2 = judge(root->right,ans);
if(abs(ans1-ans2)>1) ans=false;
return max(ans1,ans2)+1;
}
else return 0;
}
bool isBalanced(TreeNode* root) {
bool ans = true;
judge(root,ans);
return ans;
}
};
1、计算左子树元素个数left。
2、 left+1 = K，则根节点即为第K个元素
left >=k, 则第K个元素在左子树中，
left +1 <k, 则转换为在右子树中，寻找第K-left-1元素。
int calcTreeSize(TreeNode* root){
if (root == NULL)
return 0;
return 1+calcTreeSize(root->left) + calcTreeSize(root->right);
}
int kthSmallest(TreeNode* root, int k) {
if (root == NULL)
return 0;
int leftSize = calcTreeSize(root->left);
if (k == leftSize+1){
return root->val;
}else if (leftSize >= k){
return kthSmallest(root->left,k);
}else{
return kthSmallest(root->right, k-leftSize-1);
}
}
size_t _LeafSize(Node* root)
{
if (root == NULL)
{
return 0;
}
if (root->_letf == NULL &&root->_right == NULL)
{
return 1;
}
size_t i = _LeafSize(root->_letf);
size_t j = _LeafSize(root->_right);
return i + j;
}
size_t _GetKLevel(Node* root, size_t k)
{
if (root == NULL)
{
return 0;
}
if (k == 1)
{
return 1;
}
// 此处递归的意义为:某个节点的第n层节点实际上是其孩子节点的第n-1层节点
return _GetKLevel(root->_letf, k - 1) + _GetKLevel(root->_right, k - 1);
}
网友评论