二叉树的题目通常都是通过递归的方式来解决。
https://leetcode.com/explore/interview/card/top-interview-questions-easy/94/trees
题目1: 求二叉树的高度
解法
左右子树的深度较大的那一个+1
题目2: 验证一个树是不是合法的搜索二叉树
解法
递归求子树的是否合法，且返回子树中的最大最小值。
如果左右子树都合法，且左子树的最大值<当前节点值<右子树的最小值，则当前节点的树合法，且最小值为左子树的最小值，最大值为右子树的最大值。
题目3: 判断一棵树是否对称
解法
判断两棵树是否对称可以递归：一棵树的左子树与另一棵树的右子树对比。
判断一棵树是否对称，只要当作是两棵树，判断这棵树与他本身是否对称即可。
题目4: 按层输出二叉树
解法
广度优先遍历。用一个队列，首先把根结点放入，然后进入循环：从队列中取出节点访问，并将其左右子树插入队尾。
因为这里要分层，所以需要感知什么时候一层遍历结束，只需要将根结点放入队列时，再插入一个 特殊标志，比如null。每当从队列中取到null时，代表一层结束，再将其插入队尾。
题目5: 将一个有序数组转为平衡二叉搜索树
解法
将中间的数拿出来做树根，左右两部分分别作为两个子树递归即可。
网友评论