106. 从中序与后序遍历序列构造二叉树 Construct-binary-tree-from-inorder-and-postorder-traversal


给定两个整数数组 inorder 和 postorder ,其中 inorder 是二叉树的中序遍历, postorder 是同一棵树的后序遍历,请你构造并返回这颗 二叉树 。


示例 1:

15379124322b920622c4c14ba7984ef3.jpeg

输入:inorder = [9,3,15,20,7], postorder = [9,15,7,20,3]

输出:[3,9,20,null,null,15,7]


示例 2:

输入:inorder = [-1], postorder = [-1]

输出:[-1]


提示:

   1 <= inorder.length <= 3000

   postorder.length == inorder.length

   -3000 <= inorder[i], postorder[i] <= 3000

   inorder 和 postorder 都由 不同 的值组成

   postorder 中每一个值都在 inorder 中

   inorder 保证是树的中序遍历

   postorder 保证是树的后序遍历


代码: 递归

输出:

[[3] [9 20] [15 7]]




107. 二叉树的层序遍历 II  Binary Tree Level-order Traversal II


给你二叉树的根节点 root ,返回其节点值 自底向上的层序遍历 。 (即按从叶子节点所在层到根节点所在的层,逐层从左向右遍历)

示例 1:

549306189f40570a154556c180d2857f.jpeg



输入:root = [3,9,20,null,null,15,7]

输出:[[15,7],[9,20],[3]]


示例 2:

输入:root = [1]

输出:[[1]]


示例 3:

输入:root = []

输出:[]


提示:

   树中节点数目在范围 [0, 2000] 内

   -1000 <= Node.val <= 1000

代码1:  BFS

输出:

[[15 7] [9 20] [3]]

代码2:  DFS




代码3:  BFS + Queue




108. 将有序数组转换为二叉搜索树 Convert SortedArray To BinarySearchTree


给你一个整数数组 nums ,其中元素已经按 升序 排列,请你将其转换为一棵 高度平衡 二叉搜索树。

高度平衡 二叉树是一棵满足「每个节点的左右两个子树的高度差的绝对值不超过 1 」的二叉树。

示例 1:


d8563e472b4d770cf446733722485fd3.jpeg



输入:nums = [-10,-3,0,5,9]

输出:[0,-3,9,-10,null,5]

解释:[0,-10,5,null,-3,null,9] 也将被视为正确答案:

77a053e2364f50db1b393fa7799f81ba.jpeg

示例 2:

7a02bd8f1ef9548420df428cf691dd1f.jpeg

输入:nums = [1,3]

输出:[3,1]

解释:[1,null,3] 和 [3,1] 都是高度平衡二叉搜索树。


提示:

   1 <= nums.length <= 104

   -104 <= nums[i] <= 104

   nums 按 严格递增 顺序排列

代码1:

输出:

[0,-3,9,-10,null,5]

[3,1]

代码2:


输出:

[0,-10,5,null,-3,null,9]

[1,null,3]