二叉树的各种操作

发表于 | 更新于 | 阅读次数：

本篇文章针对面试中常见的二叉树操作做个总结：

1、 二叉树的遍历（前序、中序、后序、层次）
2、 求树的节点数目
3、 求树的叶子节点数目
4、 求树的深度
5、 求二叉树第k层节点个数
6、 求二叉树镜像
7、 求两个节点的最低公共祖先节点
8、 求任意两节点间距离、最长距离
9、 二叉树前序中序 推导后序

二叉树遍历

前序遍历

前序遍历即根节点在前： 根 -> 左 -> 右 1-2-4-5-3-6

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
// 递归实现
public static <T> void preOrder(TreeNode<T> root){
	if (root == null) return;
	System.out.println(root.data);
	preOrder(root.left);
	preOrder(root.right);
}

// 非递归实现
public static <T> void preOrder01(TreeNode<T> root) {
	if (root == null) return;
	LinkedList<T> stack = new LinkedList<>();
	stack.push(root);
	while(!stack.isEmpty()){
		TreeNode<T> node = stack.pop();
		System.out.println(node.data);
		if (node.right!=null) {
			stack.push(root.right);
		}
		if (node.left!=null) {
			stack.push(root.left);
		}
	}
}

中序遍历

前序遍历即根节点在前： 左 -> 根 -> 右 4-2-5-1-6-3

1
2
3
4
5
6
7
8
9
10
11
12
// 递归实现
public static <T> void inOrder(TreeNode<T> root) {
	if(root == null) return;
	inOrder(root.left);
	System.out.println(root.data);
	inOrder(root.right);
}

// 非递归实现
public static <T> void inOrder01(TreeNode<T> root) {
	
}