树相关算法

一、简介

树是一种非线性的数据结构，它是若干个有父子关系的节点的有限集合。与树相关的主要概念有：

• 节点

  树的最基本组成单元，通常包括一个数据元素和若干指向其他节点的指针。没有父节点的节点称为根节点，没有子节点的节点称为叶子节点。

• 节点的度

  节点拥有的子树的个数。

• 树的度

  树中最大的节点的度。

• 树的层次

  根节点为第一层，根节点的孩子节点为第二层，依此类推。

• 树的高度(深度)

  树中节点的最大层次数。

树有多种不同类型，主要可以分为：

• 二叉树

  每个节点最多只能有两个子节点的树。

• 二叉搜索树

  Binary Search Tree，也称为二叉查找树、二叉排序树；对于它的每个节点来说，左子树上所有节点的值都小于它的值，右子树上所有节点的值都大于它的值。

• 满二叉树

  每一层上的节点数都达到最大值的二叉树。

• 完全二叉树

  除最后一层外，每一层的节点数均达到最大值。

• AVL树

  一种自平衡的二叉搜索树，任何节点的两个子树的高度最大差值为1。

• 红黑树

  也是一种自平衡的二叉搜索树，通过颜色和一系列调整规则来确保树的平衡。

二、算法题

• 树模型类

public class TreeNode {

	int data;
	TreeNode lchild;
	TreeNode rchild;
	
	public TreeNode(int data) {
		this.data = data;
	}

	/**
	 * 数组生成树
	 * @param datas
	 * @return
	 */
	public static TreeNode createTree(Integer[] datas){
		TreeNode[] nodes = new TreeNode[datas.length];
		for(int i = 0; i < datas.length; i++){
			if(datas[i] == null){
				continue;
			}			
			TreeNode node = new TreeNode(datas[i]);
			nodes[i] = node;
			if(i == 0){
				continue;
			}
			int pidx = 0;
			boolean isRight = i % 2 == 0;
			if(isRight){
				pidx = (i - 2) / 2;
			}else{
				pidx = (i - 1) / 2;
			}
			TreeNode parent = nodes[pidx];
			if(isRight){
				parent.rchild = node;
			}else{
				parent.lchild = node;
			}
		}
		return nodes[0];
	}

	/**
	 * 层序遍历
	 */
	public void levelPrint(){
		Queue<TreeNode> queue = new LinkedList<>();
		queue.add(this);
		while(!queue.isEmpty()){
			TreeNode node = queue.poll();
			System.out.print(node.data + " ");
			if(node.lchild != null){
				queue.offer(node.lchild);
			}
			if(node.rchild != null){
				queue.offer(node.rchild);
			}
		}
	}
	
	/**
	 * 中序遍历
	 */
	public void midPrint(){
		if(this.lchild != null){
			this.lchild.midPrint();
		}
		System.out.print(this.data + " ");
		if(this.rchild != null){
			this.rchild.midPrint();
		}
	}
}

1、树的遍历

• 前序遍历

递归：

public static void main(String[] args) {
	TreeNode tree = TreeNode.createTree(new Integer[]{1, 2, 3, 4, 5, 6, 7});
	dfs(tree);
}

private static void dfs(TreeNode tree){
	if(tree == null){
		return;
	}
	System.out.print(tree.data + " ");
	dfs(tree.lchild);
	dfs(tree.rchild);
}

迭代：

public static void main(String[] args) {
	TreeNode tree = TreeNode.createTree(new Integer[]{1, 2, 3, 4, 5, 6, 7});
	Stack<TreeNode> stack = new Stack<>();
	TreeNode cur = tree;
	while(cur != null || !stack.isEmpty()){
		while(cur != null){
			System.out.print(cur.data + " ");
			stack.push(cur);
			cur = cur.lchild;
		}
		cur = stack.pop();
		cur = cur.rchild;
	}
}

输出：

1 2 4 5 3 6 7 

• 中序遍历

递归：

public static void main(String[] args) {
	TreeNode tree = TreeNode.createTree(new Integer[]{1, 2, 3, 4, 5, 6, 7});
	dfs(tree);
}

private static void dfs(TreeNode tree){
	if(tree == null){
		return;
	}
	dfs(tree.lchild);
	System.out.print(tree.data + " ");
	dfs(tree.rchild);
}

迭代：

public static void main(String[] args) {
	TreeNode tree = TreeNode.createTree(new Integer[]{1, 2, 3, 4, 5, 6, 7});
	Stack<TreeNode> stack = new Stack<>();
	TreeNode cur = tree;
	while(cur != null || !stack.isEmpty()){
		while(cur != null){
			stack.push(cur);
			cur = cur.lchild;
		}
		cur = stack.pop();
		System.out.print(cur.data + " ");
		cur = cur.rchild;
	}
}

输出：

4 2 5 1 6 3 7 

• 后序遍历

递归：

public static void main(String[] args) {
	TreeNode tree = TreeNode.createTree(new Integer[]{1, 2, 3, 4, 5, 6, 7});
	dfs(tree);
}

private static void dfs(TreeNode tree){
	if(tree == null){
		return;
	}
	dfs(tree.lchild);
	dfs(tree.rchild);
	System.out.print(tree.data + " ");
}

迭代：

public static void main(String[] args) {
	TreeNode tree = TreeNode.createTree(new Integer[]{1, 2, 3, 4, 5, 6, 7});
	Stack<TreeNode> stack = new Stack<>();
	TreeNode cur = tree;
	TreeNode prev = null;
	while(cur != null || !stack.isEmpty()){
		while(cur != null){
			stack.push(cur);
			cur = cur.lchild;
		}
		cur = stack.peek();
		if(cur.rchild != null && cur.rchild != prev){
			cur = cur.rchild;
		}else{
			stack.pop();
			System.out.print(cur.data + " ");
			prev = cur;
			cur = null;
		}
	}
}

输出：

4 5 2 6 7 3 1 

2、数组转树

将有序的整数数组放到二叉树中。

public static void main(String[] args) {
	int[] arr = {1, 2, 3, 4, 5, 6, 7};
	TreeNode root = arrayToTree(arr, 0, arr.length - 1);
	root.levelPrint();
	System.out.println();
	root.midPrint();
}

private static TreeNode arrayToTree(int[] arr, int start, int end){
	if(start > end){
		return null;
	}
	int midIdx = (start + end) / 2;
	int data = arr[midIdx];
	TreeNode root = new TreeNode(data);
	root.lchild = arrayToTree(arr, start, midIdx - 1);
	root.rchild = arrayToTree(arr, midIdx + 1, end);
	return root;
}

输出：

4 2 6 1 3 5 7 
1 2 3 4 5 6 7 

3、判断数组是否是二叉查找树后序遍历

判断一个数组是否是二叉查找树后序遍历的序列。

public static void main(String[] args) {
	int[] arr = {1, 3, 2, 5, 7, 6, 4};
	boolean ret = isAfterOrder(arr, 0, arr.length - 1);
	System.out.println(ret);//true
}

private static boolean isAfterOrder(int[] arr, int start, int end) {
	int root = arr[end];
	int i = start;
	for(; i < end; i++){
		if(arr[i] > root){
			break;
		}
	}
	
	boolean left = true;
	if(i > start){
		left = isAfterOrder(arr, start, i - 1);
	}
	boolean right = true;
	if(i < end - 1){
		right = isAfterOrder(arr, i, end - 1);
	}
	return left && right;
}

4、计算层平均值

计算树中每一层的平均数。

public static void main(String[] args) {
	TreeNode root = TreeNode.createTree(new Integer[] {3,9,20,null,null,15,7});
	List<Double> avgs = new ArrayList<>();
	List<TreeNode> arr = new LinkedList<TreeNode>();
	arr.add(root);
	while(!arr.isEmpty()){
		int sum = 0;
		int size = arr.size();
		List<TreeNode> next = new LinkedList<>();
		for(TreeNode node : arr){
			sum += node.data;
			if(node.lchild != null){
				next.add(node.lchild);
			}
			if(node.rchild != null){
				next.add(node.rchild);
			}
		}
		arr.clear();
		arr.addAll(next);
		avgs.add(sum * 1.0 / size);
	}
	System.out.println(avgs);
}

输出:

[3.0, 14.5, 11.0]

5、找到第一个大于中间值的数

在二叉搜索树中找出第一个大于中间值的数，中间值=(最小值+最大值)/2。

public static void main(String[] args) {
	TreeNode root = TreeNode.createTree(new Integer[]{4, 2, 6, 1, 3, 5, 7});
	
	TreeNode temp = root;
	while(temp.lchild != null){
		temp = temp.lchild;
	}
	int min = temp.data;
	
	temp = root;
	while(temp.rchild != null){
		temp = temp.rchild;
	}
	int max = temp.data;
	
	int mid = (min + max) / 2;
	
	temp = root;
	int ret = 0;
	while(temp != null){
		if(temp.data <= mid){
			temp = temp.rchild;
		}else{
			ret = temp.data;
			temp = temp.lchild;
		}
	}
	
	System.out.println(ret);//5
}

6、二叉搜索树的最小绝对差

计算二叉搜索树中父子节点之差的最小绝对值(二叉搜索树的中序遍历为有序递增序列)。

public static void main(String[] args) {
	TreeNode root = TreeNode.createTree(new Integer[] {3,0,48,null,null,12,50});
	dfs(root);
	System.out.println(ret);
}

private static Integer prev = null;
private static int ret = Integer.MAX_VALUE;

private static void dfs(TreeNode root){
	if(root == null){
		return;
	}
	
	dfs(root.lchild);
	
	if(prev != null){
		ret = Math.min(ret, root.data - prev);
	}
	prev = root.data;
	
	dfs(root.rchild);
	
}

输出2，即50-48的值。

7、二叉树所有路径

计算出二叉树的所有路径。

public static void main(String[] args) {
	TreeNode root = TreeNode.createTree(new Integer[] {1,2,3,null,5});
	List<String> paths = new ArrayList<>();
	collectPaths(root, "", paths);
	for(String path : paths){
		System.out.println(path);
	}
}

private static void collectPaths(TreeNode root, String path, List<String> paths) {
	if(root == null){
		return;
	}
	path = new StringBuilder(path).append(root.data).toString();
	if(root.lchild == null && root.rchild == null){
		paths.add(path);
	}else{
		collectPaths(root.lchild, path, paths);
		collectPaths(root.rchild, path, paths);
	}
}

输出：

125
13

8、计算节点数

计算二叉数的节点数。

public static void main(String[] args) {
	TreeNode root = TreeNode.createTree(new Integer[] {1,2,3,4,5,6});
	int count = countNodes(root);
	System.out.println(count);//6
}

private static int countNodes(TreeNode root) {
	if(root == null){
		return 0;
	}
	return countNodes(root.lchild) + countNodes(root.rchild) + 1;
}

9、计算最长距离

计算任意两个节点之间的最长距离。

private static int ret = 0;
	
public static void main(String[] args) {
	TreeNode node = TreeNode.createTree(new Integer[] {1,2,3,4,5,6});
	calcMaxPath(node);
	System.out.println(ret);//4
}

private static int calcMaxPath(TreeNode node) {
	if(node == null){
		return 0;
	}
	int left = calcMaxPath(node.lchild);
	int right = calcMaxPath(node.rchild);
	
	int val = left + right + 1;
	
	if(val - 1 > ret){
		ret = val - 1;
	}
	
	return Math.max(left, right) + 1;
}

10、复制二叉树

public static void main(String[] args) {
	TreeNode tree = TreeNode.createTree(new Integer[]{1, 2, 3, 4, 5, 6, 7});
	copy(tree).levelPrint();
}

private static TreeNode copy(TreeNode root){
	if(root == null){
		return null;
	}
	TreeNode copy = new TreeNode(root.data);
	copy.lchild = copy(root.lchild);
	copy.rchild = copy(root.rchild);
	return copy;
}

输出：

1 2 3 4 5 6 7 

11、修剪二叉树

如果叶子节点为0，则修剪掉。

public static void main(String[] args) {
	TreeNode root = TreeNode.createTree(new Integer[] {1, 0, 0, 0, 0, 0, 1});
	prune(root).levelPrint();
}

private static TreeNode prune(TreeNode root){
	
	if(root == null){
		return null;
	}
	
	//后序遍历
	root.lchild = prune(root.lchild);
	root.rchild = prune(root.rchild);
	
	if(root.lchild == null && root.rchild == null && root.data == 0){
		return null;
	}
	
	return root;
}

输出：

1 0 1

12、镜像反转

对二叉树进行镜像反转，例如：

镜像反转后为：

public static void main(String[] args) {
	TreeNode root = TreeNode.createTree(new Integer[]{4, 2, 6, 1, 3, 5, 7});
	reverse(root);
	root.levelPrint();
}

private static void reverse(TreeNode root) {
	if(root == null){
		return;
	}
	
	TreeNode temp = root.lchild;
	root.lchild = root.rchild;
	root.rchild = temp;
	
	reverse(root.lchild);
	reverse(root.rchild);
}

13、判断是否是平衡树

判断二叉树是否是平衡树，即左右子树高度差不超过1。

public static void main(String[] args) {
	TreeNode root = TreeNode.createTree(new Integer[] {3,9,20,null,null,15,7});
	System.out.println(isBlanced(root));//true
}

private static boolean isBlanced(TreeNode root) {
	if(root == null){
		return true;
	}else{
		boolean blanced = Math.abs(getHeight(root.lchild) - getHeight(root.rchild)) <= 1;
		return blanced && isBlanced(root.lchild) && isBlanced(root.rchild);
	}
}

private static int getHeight(TreeNode root){
	if(root == null){
		return 0;
	}else{
		return Math.max(getHeight(root.lchild), getHeight(root.rchild)) + 1;
	}
}

14、判断是否是子树

判断一个树是否是另一个树的子树。

public static void main(String[] args) {
	TreeNode s = TreeNode.createTree(new Integer[] {3,4,5,1,2});
	TreeNode t = TreeNode.createTree(new Integer[] {4, 1, 2});
	System.out.println(isSubTree(s, t));//true
}

private static boolean isSubTree(TreeNode s, TreeNode t) {
	if(s == null && t == null){
		return true;
	}
	if(s == null || t == null){
		return false;
	}
	
	return isSame(s, t) || isSubTree(s.lchild, t) || isSubTree(s.rchild, t);
}

private static boolean isSame(TreeNode s, TreeNode t) {
	if(s == null && t == null){
		return true;
	}
	if(s == null || t == null){
		return false;
	}
	return s.data == t.data && isSame(s.lchild, t.lchild) && isSame(s.rchild, t.rchild);
}

15、判断树是否对称

判断树是否是对称二叉树。

public static void main(String[] args) {
	TreeNode root = TreeNode.createTree(new Integer[] {1, 2, 2, 3, 4, 4, 3});
	System.out.println(isSymmetric(root));//true
}

private static boolean isSymmetric(TreeNode root) {
	if(root.lchild == null && root.rchild == null){
		return true;
	}
	if(root.lchild == null || root.rchild == null){
		return false;
	}
	return check(root.lchild, root.rchild);
}

private static boolean check(TreeNode lchild, TreeNode rchild) {
	if(lchild == null && rchild == null){
		return true;
	}
	if(lchild == null || rchild == null){
		return false;
	}
	return lchild.data == rchild.data && check(lchild.lchild, rchild.rchild) && check(lchild.rchild, rchild.lchild);
}

16、判断是否存在和为某个值的两个数

判断二叉树中是否存在两个数，使它们的和等于给定的值。

private static Set<Integer> set = new HashSet<>();

public static void main(String[] args) {
	TreeNode tree = TreeNode.createTree(new Integer[]{1, 2, 3, 4, 5, 6, 7});
	int target = 12;
	System.out.println(find(tree, target));//true
}

private static boolean find(TreeNode root, int target) {
	if(root == null){
		return false;
	}
	if(set.contains(target - root.data)){
		return true;
	}
	set.add(root.data);
	return find(root.lchild, target) || find(root.rchild, target);
}

17、找和最大的路径

在二叉树中找出路径最大的和，路径可以以任意结点作为起点和终点

private static int ret = Integer.MIN_VALUE;
	
public static void main(String[] args) {
	TreeNode tree = TreeNode.createTree(new Integer[]{6, 3, -7, -1, 9});
	findMaxPath(tree);
	System.out.println(ret);//18
}

private static int findMaxPath(TreeNode tree) {
	if(tree == null){
		return 0;
	}
	int left = findMaxPath(tree.lchild);
	int right = findMaxPath(tree.rchild);
	
	int leftData = left + tree.data;
	int rightData = right + tree.data;
	int allData = left + right + tree.data;
	
	int max = leftData > rightData ? leftData : rightData;
	max = max > allData ? max : allData;
	
	if(max > ret){
		ret = max;
	}
	
	return (left > right ? left : right) + tree.data;
}

18、计算最大子树和

计算二叉树的最大子树和。

private static int ret = Integer.MIN_VALUE;
	
public static void main(String[] args) {
	TreeNode root = TreeNode.createTree(new Integer[]{6, 3, -7, -1, 9});
	dfs(root);
	System.out.println(ret);//11
	
}
private static int dfs(TreeNode root) {
	if(root == null){
		return 0;
	}
	
	int left = dfs(root.lchild);
	int right = dfs(root.rchild);
	
	int val = left + right + root.data;
	
	if(val > ret){
		ret = val;
	}
	
	return val;
}

19、找到符合条件的路径

在二叉树中找出与指定整数相等的路径。

public static void main(String[] args) {
	TreeNode tree = TreeNode.createTree(new Integer[]{6, 3, -7, -1, 9});
	List<Integer> paths = new ArrayList<>();
	int target = 8;
	dfs(tree, 0, target, paths);
}

private static void dfs(TreeNode node, int sum, int target, List<Integer> paths){
	if(node == null){
		return;
	}
	int val = node.data;
	sum += val;
	paths.add(val);
	
	if(node.lchild != null){
		dfs(node.lchild, sum, target, paths);
	}
	if(node.rchild != null){
		dfs(node.rchild, sum, target, paths);
	}
	
	if(node.lchild == null && node.rchild == null && sum == target){
		for(int i : paths){
			System.out.print(i + " ");
		}
		System.out.println();
	}
	
	int idx = paths.size() - 1;
	sum -= paths.get(idx);
	paths.remove(idx);
}

20、计算所有路径之和

计算二叉树所有路径(根节点到叶子节点)表示的数字之和。

public static void main(String[] args) {
	TreeNode root = TreeNode.createTree(new Integer[] {3, 9, 0, 5, 1, null, 2});
	System.out.println(dfs(root, 0));//1088
}

private static int dfs(TreeNode root, int val){
	if(root == null){
		return 0;
	}
	
	val = val * 10 + root.data;
	if(root.lchild == null && root.rchild == null){
		return val;
	}
	
	return dfs(root.lchild, val) + dfs(root.rchild, val);
}