102. 二叉树的层次遍历

题目描述 给定一个二叉树,返回其按层次遍历的节点值。 (即逐层地,从左到右访问所有节点)。 例如:给定二叉树: [3,9,20,null,null,15,7], 3 / \ 9 20 / \ 15 7 返回其层次遍历结果: [ [3], [9,20], [15,7] ] https://leetcode-cn.com/problems/binary-tree-level-order-traversal/ 解法1 – BFS 解法1不用多说,在课本中,考研题中经常出现。我们使用队列,将跟节点加入队列,然后出队并访问,再将出队节点的左右子树再一次加入队列……直到队列为空。这种解法很自然,也很容易想到。 时间复杂度O(n),空间复杂度O(n)。全部代码如下: 解法2 – DFS 这道题也可以采用DFS解法,层次其实就是深度,我们记录遍历到每一层级到深度,为每一层级创建List,根据当前深度找到对应的List,然后追加进去。在实现的时候,我们采用先序遍历的,如果采用中序/后序遍历,下面的代码需要略微调整,将if改为while。因为先序遍历能够保证为深度比当前节点浅的所有节点都创建相应的List。而中序/后序遍历会先走到最深的左/右子树,我们必须使用循环为所有层级比当前浅的节点创建对应的List。 DFS理论上会比BFS慢一些,因为存在函数调用与调用栈创建等开销。此外,如果树的层级过高,会有“爆栈”的风险。时间复杂度O(n),空间复杂度O(n)。全部代码如下:

Read more

Leetcode 144/94/145 – 二叉树的前序/中序/后续遍历

题目1描述 给定一个二叉树,返回它的 前序 遍历。  示例: 输入: [1,null,2,3] 1 \ 2 / 3 输出: [1,2,3] 进阶: 递归算法很简单,你可以通过迭代算法完成吗? https://leetcode-cn.com/problems/binary-tree-preorder-traversal/ 解法1 – 递归算法 递归解法:定义一个函数private void preorder(TreeNode node, List ans),如果node为空则返回,否则将node.val添加到ans中。然后依次递归调用preorder(node.left, ans)访问node的左子树;递归调用preorder(node.right, ans)访问node的右子树。 时间复杂度O(n),空间复杂度O(n)(递归过程中会创建调用栈,实际上还是有额外空间的),其中n为二叉树节点数量。全部代码如下: 解法2 – 迭代算法 我们创建栈stack,首先将跟节点入栈,然后取出栈顶元素node访问,将node.val加入到结果数组ans中。然后,我们将右子树、左子树依次入栈(如果他们不为空)。因为先序遍历需要依次访问跟节点、左子树、右子树,所以我们需要先将右子树入栈,再将左子树入栈。 时间复杂度O(n),空间复杂度O(n)。全部代码如下: 题目2描述 给定一个二叉树,返回它的中序 遍历。 示例: 输入: [1,null,2,3] 1 \ 2 / 3 输出: [1,3,2] 进阶: 递归算法很简单,你可以通过迭代算法完成吗? https://leetcode-cn.com/problems/binary-tree-inorder-traversal/ 解法1 – 递归算法 和题目1的递归算法类似,我们只需要调整访问node的顺序,使其先递归访问node的左子树;然后将node.val加入到结果数组;最后递归访问node的右子树即可。 时间复杂度O(n),空间复杂度O(n)。全部代码如下: 解法2 – 迭代算法 为了能够将递归算法转化为迭代算法,我们需要模拟调用栈的过程。中序遍历要求最先访问左子树,那我们就创建栈stack,变量node指向当前节点,一直向左下角走,将沿途的节点都加入到stack中,直到走到空节点。当走到空节点时,我们从栈中弹出一个节点并访问,这就是第一个被访问的左子节点。然后我们将node指向node的右子树(node =…

Read more