Leecode 110 平衡二叉树

给定一个二叉树，判断它是否是平衡二叉树

思考部分：

1.判断一个二叉树是否是平衡二叉树的标准是什么

2.代码书写

/** *Definition for a binary tree node. *struct TreeNode *{ * int val; * struct TreeNode *left; * struct TreeNode *right; *}; */ #include<stdio.h> #include<stdbool.h> #include<stdlib.h> #include<math.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 （leftHeight>rightHeight ?leftHeight :rightHeight）+1; } bool isBanlanced(struct TreeNode* root) { return getHeight(root)!=-1; }

1.为什么不采用自顶向下的写法呢？

答：遍历每个节点，算它的左右子树高度的时候要重复遍历多次，根节点，左孩子，右孩子，每个节点都会被重复访问，时间复杂度O（n^2）,如果是自底向上的遍历，每个节点只访问一次即可。

2.为什么返回值用int 而不是bool?

答：树的高度是大于等于0的整数，返回-1的时候就已经代表此树不平衡了，这样用一个int,保证了返回值高度大于等于0，又返回了平衡状态-1，省去了额外传递状态变量的麻烦

3.为什么要先递归左子树，再递归右子树（后序遍历）

要判断当前节点是否平衡，必须依赖两个数据：左子树高度高度和右子树高度。

如果不先递归到底，就拿不到子树的高度，所以代码顺序必须是：递归左孩子——>递归右孩子——>处理当前节点，保证了在计算根节点的时候，孩子节点的信息已经完全就绪

4.为什么要每次递归完都要判断if(leftHeight == -1) ?(剪枝优化)

如果左子树已经不平衡了，那棵树肯定不平衡，右子树根本不需要再计算了

这里的return -1 叫做提前终止（剪枝）。它避免了无谓的递归，能把最坏情况的时间复杂度从O（n^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, *pB=headB; 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） cur=copy ->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; }