Top 100 Linked Question 修炼------第226题、第234题
226. Invert Binary Tree
题目解释:翻转一棵二叉树。
Example:
Input:
4 / 2 7 / / 1 3 6 9
Output:
4 / 7 2 / / 9 6 3 1
题目分析:首先最简单的就是采用递归的方式:我们需要翻转一棵二叉树,首先即是需要对其左子树进行翻转,然后反转根节点的右子树,最后将根节点的左右子树进行翻转即可达到我们最后的目的:
# class TreeNode: # def __init__(self, x): # self.val = x # self.left = None # self.right = None class Solution: def invertTree(self, root: TreeNode) -> TreeNode: if root: # 翻转左子树 self.invertTree(root.left) # 翻转右子树 self.invertTree(root.right) # 左子树和右子树进行对换 temp=root.left root.left=root.right root.right=temp return root
当考虑到可能递归溢出的情况下,递归的程序也可以改写成非递归。结合本题的特点可知,我们需要的是调换左右子树,那么是不是可以采用队列的形式,若某个结点的左右子树不为空,那么就是可以交换左右结点,然后将非空的左右子树加入到队列中:
class Solution(object): def invertTree(self, root): """ :type root: TreeNode :rtype: TreeNode """ if (root is None): return None q = [root] while (q): curr = q.pop(0) # 交换结点的位置 temp = curr.left curr.left = curr.right curr.right = temp # 将左右结点加入到队列中 if (curr.left is not None): q.append(curr.left) if (curr.right is not None): q.append(curr.right) return root
234. Palindrome Linked List
题目解释:
Given a singly linked list, determine if it is a palindrome.
Example 1:
Input: 1->2 Output: false
Example 2:
Input: 1->2->2->1 Output: true
题目分析:本题是比较简单的,可以直接想到这种思路:
首先是遍历一遍,取得整个链表的长度,然后取一半的数据,将其入栈,最后每次出一次栈,最后一半的数据中,我们可以一遍遍历一边出栈,同时判断栈顶元素是否和当前遍历的数据是否相同,若相同,则继续遍历下去,若不相同,则不是回文链表。
虽然这样的想法是比较容易实现的,但是我们回头自己看下题目要求:
Could you do it in O(n) time and O(1) space?
显然,题目最终是想要我们去完成这个题目是在O(n)的时间复杂度,并且是O(1)的空间复杂度,是不能借助于栈的。
好吧,那我们再继续另外想办法:既然我们不能借助于额外的栈,那么是不是可以先将链表的一部分反转,然后将反转的一部分链表和未反转的那一部分链表进行比较,若两个链表完全相同,那么就是回文链表,否则就不是回文链表。
class Solution(object): def isPalindrome(self, head): """ :type head: ListNode :rtype: bool """ # 定义快慢指针,当快指针走到尾部时,慢指针是走到链表的中间部分 fast=slow=head while fast and fast.next: slow=slow.next fast=fast.next.next # 反转部分链表 node=None while slow: nxt=slow.next slow.next=node node = slow slow=nxt # 比较链表是否相同 while node: if node.val != head.val: return False node = node.next head = head.next return True
总结
2019/5/16:今天又是元气满满的一天呐