一周编程集训day4：二叉树
一周编程集训day4：二叉树
1 任务
二叉树：学习三种遍历(前、中、后)及层次遍历，并完成leetcode上的验证二叉搜索树(98)及二叉树 层次遍历(102,107)！并同时温习前三天内容，做出总结！
2 概念介绍
- 二叉树概念：一棵二叉树是结点的一个有限集合。该集合或者为空，或者是由一个根节点加上两棵分别称为左子树和右子树组成。
- 满二叉树：除了最后一层的节点无任何子节点外，剩下的每一层上的节点都有两个子节点。
- 完全二叉树：除了最后一层之外，其他每一层的节点数都是满的，最后一层如果也是满的，则是一棵满二叉树，也是完全二叉树。最后一层如果不满，则缺少的节点也全部都集中在右边，那也是一棵完全二叉树。
判断是否是完全二叉树的步骤：
1）层序遍历二叉树；
2）如果存在一个节点的右子树存在而左子树不存在，则直接返回false
3）如果当前节点的左子树和右子树不同时存在，则其后的节点的左右子树均不存在，如果存在，则直接返回false
4）如果顺利遍历结束，则直接返回true
- 二叉树的遍历：遵循某种次序，遍历二叉树中的所有节点，使得每个结点被访问一次，而且仅访问一次。“访问”：即对结点施行某些操作。二叉树的遍历有四种顺序。
1）先序遍历：先访问根结点，再访问左子树，最后访问右子树。
2）中序遍历：先访问左子树，再访问根结点，最后访问右子树。
3）后序遍历：先访问左子树，再访问右子树，最后访问根结点。
4）层次遍历：用一个队列保存被访问的当前节点的左右孩子以实现层序遍历。
3 leetcode
给定一个二叉树，判断其是否是一个有效的二叉搜索树。
假设一个二叉搜索树具有如下特征：
节点的左子树只包含小于当前节点的数。
节点的右子树只包含大于当前节点的数。
所有左子树和右子树自身必须也是二叉搜索树。
示例 1:
输入:
2
/ \
1 3
输出: true
示例 2:
输入:
5
/ \
1 4
/ \
3 6
输出: false
解释: 输入为: [5,1,4,null,null,3,6]。
根节点的值为 5 ，但是其右子节点值为 4 。
python解答思路：用递归的思想解决。如果节点为空，则返回True。若左子树不空的时候，其根结点大于左子树的最大值，左子树返回为真且右子树也为真则返回真；考虑右子树时，根要比右子树的最小值小。
class Solution(object):
def isValidBST(self, root):
"""
:type root: TreeNode
:rtype: bool
"""
return self.valid(root, None, None)
def valid(self, root, min, max):
if root == None or root.val == None:
return True
if (min is not None and root.val <= min) or (max is not None and root.val >= max):
print(1)
return False
return self.valid(root.left, min, root.val) and self.valid(root.right, root.val, max)
leetcode提交结果：
2. 102.二叉树的层次遍历
给定一个二叉树，返回其按层次遍历的节点值。 （即逐层地，从左到右访问所有节点）。
例如:
给定二叉树: [3,9,20,null,null,15,7],
3
/ \
9 20
/ \
15 7
返回其层次遍历结果：
[
[3],
[9,20],
[15,7]
]
python解答思路：用深度优先搜索（DFS），节点的深度与输出结果数组的下标相对应。
class Solution(object):
def levelOrder(self, root):
"""
:type root: TreeNode
:rtype: List[List[int]]
"""
res = []
self.dfs(root, 0, res)
return res
def dfs(self, root, depth, res):
if root == None:
return res
if len(res) < depth+1:
res.append([])
res[depth].append(root.val)
self.dfs(root.left, depth+1, res)
self.dfs(root.right, depth+1, res)
leetcode提交结果：
3. 107. 二叉树的层次遍历 II
给定一个二叉树，返回其节点值自底向上的层次遍历。 （即按从叶子节点所在层到根节点所在的层，逐层从左向右遍历）
例如：
给定二叉树 [3,9,20,null,null,15,7],
3
/ \
9 20
/ \
15 7
返回其自底向上的层次遍历为：
[
[15,7],
[9,20],
[3]
]
python解答思路：采用层次遍历法，并翻转。
class Solution(object):
def help(self, root, level, ans):
if root:
if len(ans) < level + 1:
ans.append([])
ans[level].append(root.val)
self.help(root.left, level + 1, ans)
self.help(root.right, level + 1, ans)
def levelOrderBottom(self, root):
"""
:type root: TreeNode
:rtype: List[List[int]]
"""
ans = []
self.help(root, 0, ans)
ans.reverse()
return ans
leetcode提交结果：