本地网站后台管理建设,大良营销网站建设特色,漳州微信网站建设,seo推广公司哪家好目录
1、是否是平衡二叉树
初阶实现
分析
时空复杂度
进阶实现
分析
时空复杂度
总结
2、翻转二叉树
分析
时空复杂度 1、是否是平衡二叉树
110. 平衡二叉树 - 力扣#xff08;LeetCode#xff09;
初阶实现
/*** Definition for a binary tree node.* stru…目录
1、是否是平衡二叉树
初阶实现
分析
时空复杂度
进阶实现
分析
时空复杂度
总结
2、翻转二叉树
分析
时空复杂度 1、是否是平衡二叉树
110. 平衡二叉树 - 力扣LeetCode
初阶实现
/*** Definition for a binary tree node.* struct TreeNode {* int val;* struct TreeNode *left;* struct TreeNode *right;* };*/
int height(struct TreeNode* root) {if (root NULL) {return 0;} else {return fmax(height(root-left), height(root-right)) 1;}
}bool isBalanced(struct TreeNode* root) {if (root NULL) {return true;} else{//递归祖先结点的整个左子树的左右子树并计算整个左子树的深度、以及整个右子树的左右子树并计算整个左右子树的深度//由于一颗二叉树是平衡二叉树则它的所有子树也都是平衡二叉树return fabs(height(root-left) - height(root-right)) 1 isBalanced(root-left) isBalanced(root-right);}
}
分析 首先要知道的是一颗树是否为平衡二叉树在于它的左右子树的高度查是否为1我们首先利用递归宏观的计算整棵树的左子树和右子树的高度差height函数中fmax函数的作用就是选出当前结点的左右子树的最大深度然后加一得到当前结点及其左右子树的整体高度然后将该高度返回fabs函数计算的是整棵树左右子树的高度差的绝对值如果该绝对值小于等于1那么宏观上看该树是一颗平衡二叉树但是微观上我们无法保证所以在使用fabs函数后还需要递归判断整棵树的左右子树是否是一颗平衡二叉树它们的子树是否是一颗平衡二叉树......平衡二叉树的所有子树均为平衡二叉树 时空复杂度 时间复杂度ON^2n是二叉树中的节点个数且二叉树为链式结构(一条线)高度为nn*n 空间复杂度ON n是二叉树中的节点个数空间复杂度主要取决于递归调用的层数递归调用的层数不会超过n 进阶实现
/*** Definition for a binary tree node.* struct TreeNode {* int val;* struct TreeNode *left;* struct TreeNode *right;* };*/int height(struct TreeNode* root) {if (root NULL) {return 0;}int leftHeight height(root-left);int rightHeight height(root-right);if (leftHeight -1 || rightHeight -1 || fabs(leftHeight - rightHeight) 1) {return -1;} else {return fmax(leftHeight, rightHeight) 1;}
}
//因为自底向上的判断过程中如果某一节点不满足平衡条件那么该节点向上层父节点返回-1上层结点如果发现自己的左右结点有一个为-1就表示它知道这棵树不是平衡二叉树自己也就不再判断而直接再次向自己的上层结点返回-1所以最后根结点直接判断是不是大于零就行因为如果不是平衡二叉树最后根节点会返回-1.bool isBalanced(struct TreeNode* root) {return height(root) 0;
}分析 根据height函数的返回值判断是否是平衡二叉树在height函数中我们先递归完左子树到头时返回0并将该值用leftHeight接收然后递归当前结点的右子树如果也为空则返回0然后判断leftHeight和rightHeight以及它俩的差值的绝对值是否大于一一般来说该判断语句第一次结果为真都是因为差值绝对值大于一然后才会返回-1导致leftHeight或者rightHeight值为-1然后-1会一直传递直到整个递归结束它标志着该二叉树不是平衡二叉树当该判断语句为假时就会利用fmax函数计算当前结点作为一棵树时的高度如果该树不是平衡二叉树就会导致该高度会一直叠加从而第一次触发fabs函数然后就整体递归调用返回-1该树不为平衡二叉树 时空复杂度 时间复杂度ONn是二叉树中的节点个数每个节点的计算高度和判断是否平衡都只需要处理一次 空间复杂度ON n是二叉树中的节点个数空间复杂度主要取决于递归调用的层数递归调用的层数不会超过n 总结 自顶向下的看着很美细看由于没有记录结点存在子序列重复的情况。主函数内return封住了当前为平衡点以及左右子结点为平衡点可是每次递归都会重复对尾部到当前的第n-1高度结点重复判断导致了 n(1n)/2, 效率太低。所以还得是自下向上省去了记忆化过程天然回溯到父节点就可以得到子节点的高度 2、翻转二叉树
226. 翻转二叉树 - 力扣LeetCode
/*** Definition for a binary tree node.* struct TreeNode {* int val;* struct TreeNode *left;* struct TreeNode *right;* };*/struct TreeNode* invertTree(struct TreeNode* root) {if (root NULL) {return NULL;}struct TreeNode* left invertTree(root-left);struct TreeNode* right invertTree(root-right);root-left right;root-right left;return root;
}分析 由于二叉树是链式结构的所以更改父亲结点的同时该父亲结点的子孙结点都会跟着移动所以这里我们利用递归分别将两个要翻转的两颗子树的左右子树进行翻转然后在递归返回地过程中将两个树地父亲结点也翻转这样就完成了一次二叉树地翻转 时空复杂度 时间复杂度ONn是二叉树中的节点个数使用自底向上的递归每个节点的计算高度和判断是否平衡都只需要处理一次最坏情况下需要遍历二叉树中的所有节点 空间复杂度ON n是二叉树中的节点个数空间复杂度主要取决于递归调用的层数递归调用的层数不会超过n ~over~
