有关二叉树的练习
回顾:
二叉树的表示:
- 二叉树的结点 vs 该结点为根的一棵树
TreeNode node = root - TreeNode node = null; //没有结点
二叉树的遍历(深度优先遍历):
-
前序遍历:根 [左子树] [右子树]
-
中序遍历:[左子树] 根 [右子树]
-
后序遍历:[左子树] [右子树] 根
练习:
1.提供一棵树,数出有多少个结点
法一:
法二:
2.给定一棵树,求这棵树的叶子结点的个数
法一:
法二:
3.给定一颗二叉树,求该二叉树第k曾结点的个数(假定根的层级为1,看 >= 1 )
思路:
- 空树(无论k是多少,结果均为0)
- k == 1时,结果为1
- 其他情况
非空树 && k > 1
左子树的情况(k - 1)
右子树的情况(k - 1)
4.给定一颗二叉树树,求二叉树的高度
思考:
1.空树(高度为0)
2.一个结点的树(高度为1)
3.其他情况
如何求树的高度(左子树,右子树)
max(左子树高度,右子树高度) + 1
5.给定一棵树,同时给定一个v,问这颗二叉树中是否包含这个v