Day 26

第167题:

给定一个已按照升序排列 的有序数组,找到两个数使得它们相加之和等于目标数。

函数应该返回这两个下标值 index1 和 index2,其中 index1 必须小于 index2。来源:力扣(LeetCode)

1、已知数组时升序的,需求出两个数相加之和为target,可以先确定一个数nums[i],然后在其右边寻找合适的数target-nums[i];

  查找另一个数可以使用二分查找,降低时间复杂度。

  

2、因为数组是升序的,所以可以定义两个指针分别指向数组的首和尾;

  求出这两个数的和sum,比较sum和target的大小;

  如果大了,就将尾前移,小了,就将首后移;

  知道返回sum=target的结果。

  

第100题:

给定两个二叉树,编写一个函数来检验它们是否相同。

如果两个树在结构上相同,并且节点具有相同的值,则认为它们是相同的。(来自LeetCode)

1、判断两棵树受否相同,使用递归判断根,在判断左子树和右子树。

  

2、除了递归,也可以使用队列来辅助迭代比较两棵树是否相同;

  将两棵树的根节点依次推入队列;

  当队列不为空时,定义两个指针分别指向两棵树的根节点,比较是否相同;

  相同的话就将两树的左右节点分别依次推入队列,重复上述步骤;

  最终返回结果。(栈也可以)

    

 第102题:

给你一个二叉树,请你返回其按 层序遍历 得到的节点值。 (即逐层地,从左到右访问所有节点)。(来自LeetCode)

1、二叉树的层次遍历,和深度优先遍历差不多,但是每次需要将每层的全部节点先返回,

  深度优先遍历则是将这个节点的下一层的节点先返回,在返回这个节点的兄弟节点;

  既然我们需要优先按层数返回,可以用队列将一层的所有节点都入队,然后定义这时候队列的长度;

  使用队列长度来分层;

  例如先将根节点推入队列,此时队列长度为1,那么第一层就一个节点;

  这时候将根节点的左右儿子节点入队,此时队列长度为2,再将这两个节点依次出队;

  并将这两个节点不为空的子节点入队,这样每次入队的都是一层的节点,易于分辩层数;

  最终返回结果。

  

原文地址:https://www.cnblogs.com/liang-yi-/p/13352558.html