平衡二叉树、相交链表与随机指针链表的LeetCode经典题解析

Leecode 110 平衡二叉树给定一个二叉树判断它是否是平衡二叉树思考部分1.判断一个二叉树是否是平衡二叉树的标准是什么2.代码书写/** *Definition for a binary tree node. *struct TreeNode *{ * int val; * struct TreeNode *left; * struct TreeNode *right; *}; */ #includestdio.h #includestdbool.h #includestdlib.h #includemath.h int getHeight(struct TreeNode* root) { if(root NULL) { return 0; //空树高度为0 } //后序遍历 int leftHeight getHeight(root -left); if(leftHeight -1) return -1; //左子树不平衡提前返回 int rightHeight getHeight(root -right); if(rightHeight -1) return -1; //右子树不平衡提前返回 //检查当前节点是否平衡 if(abs(leftHeight-rightHeight)1) { return -1; } //返回当前树的高度 return leftHeightrightHeight ?leftHeight :rightHeight1; } bool isBanlanced(struct TreeNode* root) { return getHeight(root)!-1; }1.为什么不采用自顶向下的写法呢答遍历每个节点算它的左右子树高度的时候要重复遍历多次根节点左孩子右孩子每个节点都会被重复访问时间复杂度On^2,如果是自底向上的遍历每个节点只访问一次即可。2.为什么返回值用int 而不是bool?答树的高度是大于等于0的整数返回-1的时候就已经代表此树不平衡了这样用一个int,保证了返回值高度大于等于0又返回了平衡状态-1省去了额外传递状态变量的麻烦3.为什么要先递归左子树再递归右子树后序遍历要判断当前节点是否平衡必须依赖两个数据左子树高度高度和右子树高度。如果不先递归到底就拿不到子树的高度所以代码顺序必须是递归左孩子——递归右孩子——处理当前节点保证了在计算根节点的时候孩子节点的信息已经完全就绪4.为什么要每次递归完都要判断if(leftHeight -1) ?(剪枝优化)如果左子树已经不平衡了那棵树肯定不平衡右子树根本不需要再计算了这里的return -1 叫做提前终止剪枝。它避免了无谓的递归能把最坏情况的时间复杂度从On^2优化到O(n)。叶子节点如果不平衡直接层返回-1上层根本不会执行右子树的递归。5.为什么检查abs(leftHeight -rightHeight)1 ?这是平衡二叉树定义的直接翻译一棵树是平衡二叉树当且仅当任意节点的左右子树高度差的绝对值不超过1.只要当前节点不满足直接返回-1向上报告“失守”6最后一句 return max(left,right)1是做什么在确认了当前节点平衡后组要把当前这棵子树的高度返回给父节点。父节点拿到这个高度后才能计算自己与另一棵子树的高度差。1代表当前节点本身所占的一层LRC 023.相交链表1.思考部分1首先一上来如果题目给的链表A或者链表B为空那就肯定没有交点没有往下执行下去的必要了直接返回空指针。2初始化两个指针pA和pB,pA从链表A开始走pB从链表B开始走3这俩指针如果到了同一个结点或者同时为空即循环结束在循环中如果pA走到头了就立刻瞬移到B的起点否则就原地往前走一步如果pB走到头了就立刻瞬移到A的起点否则就原地往前走一步循环结束后把它俩站的那个位置交点或NULL返回出去2.代码书写/** *Definition for singly-linked list . *struct ListNode{ *int val; *struct ListNode *next; *}; */ struct ListNode *getIntersectionNode(struct ListNode *headA ,struct ListNode * headB){ if(headA NULL || headB NULL){ return NULL; } struct ListNode *pA headA, *pBheadB; while(pA ! pB){ pA pA NULL ? headB : pA-next; pB pB NULL ? headA : pB-next; } return pA; }Leecode 138 随机链表的复制思路部分代码部分/** * Definition for a Node. * struct Node{ * int val; * struct Node *next; * struct Node *random; * }; */ struct Node* copyRandomList(struct Node* head){ if(!head) return NULL; struct Node *cur head; struct Node *copy NULL; //一.在原链表的每个结点后面插入一个复制结点 while(cur) { //1.创建新结点 copy (struct Node*)malloc(sizeof(struct Node)); copy -val cur -val; copy -random NULL; //先置空 //2插入到当前结点和下一个结点之间 copy -next cur -next; cur -next copy; //3.移动到原链表的下一个结点直接跳过刚刚插入的copy cur copy -next; } //二.设置复制结点的random指针 cur head; while(cur) { //当前结点的复制结点就是cur-next copy cur-next; //如果原结点的random不为空那么复制结点的random应该指向原结点-random-next if(cur-random) { copy-random cur -random-next; } //移动到下一个原结点原链表的下一个因为中间插入了copy,所以是copy-next curcopy -next; } //三.将这条新旧交替的链表拆开恢复原链表同时提取出复制链表 cur head; struct Node *newHead head -next ; //复制链表头结点 struct Node *newCur NULL; while(cur) { copy cur-next ; //复制结点 newCur copy-next; //下一个原结点 //恢复原链表的next cur -next newCur; //连接复制链表的next if(newCur){ copy -next newCur-next ; //让copy指向下一个复制节点 }else{ copy -next NULL; } //遍历原链表 cur newCur; } return newHead; }