二叉树

Posted on | In | Visitors:

1、重建二叉树

问题描述：

输入某二叉树的前序遍历和中序遍历的结果，请重建出该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。

思路：

  • 根据前序遍历，可知根节点。

  • 根据中序遍历，可知左右子树对应的子序列。

  • 接下来，递归。

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
public class ReConstruct {
	public TreeNode reConstructBinaryTree(int[] pre, int[] in) {
		TreeNode root = reConstructBinaryTree(pre, 0, pre.length-1, in, 0, in.length-1);
		return root;
	}
	private TreeNode reConstructBinaryTree(int[] pre, int startPre, int endPre, int[] in, int startIn, int endIn) {
		if (pre == null || in == null || startPre > endPre || startIn > endIn)
			return null;
		//根节点
		TreeNode root = new TreeNode(pre[startPre]);
		for (int i = startIn; i <= endIn; i++) {
			if (in[i] == startPre) {
				root.left = reConstructBinaryTree(pre, startPre + 1, startPre + (i - startIn), in, startIn, i - 1);
				root.rifgt = reConstructBinaryTree(pre, startPre + (i - startIn) + 1, endPre, in, i + 1, endIn);
			}
		}
		retuirn root;
	}
}

2、树的子结构

问题描述：

输入两棵二叉树 A 和 B，判断 B 是不是 A 的子结构。

思路：

  • 在树 A 中找到和 B 的根结点的值一样的结点 R；（树的遍历，递归）

  • 判断树 A 中以 R 为根节点的子树是不是包含和树 B 一样的结构。（递归，终止条件是到达了树A 或者 树B 的叶结点）

即：

  1. 首先设置标志位result = false，一旦匹配成功 result 就设为 true，剩下的代码不会执行，如果匹配不成功，默认返回false；

  2. 递归思想，如果根节点相同则递归调用 DoesTree1HaveTree2（），

  3. 注意null的条件，HasSubTree中，如果两棵树都不为空才进行判断，DoesTree1HasTree2中，如果Tree2为空，则说明第二棵树遍历完了，即匹配成功，tree1为空有两种情况：（1）如果tree1为空&&tree2不为空，说明不匹配，（2）如果tree1为空，tree2为空，说明匹配。

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
public class Solution {
	// 在树A中，查找与根节点的值一样的结点
	public boolean hasSubTree(TreeNode root1, TreeNode root2) {
		boolean result = false;
		if (root1 != null && root2 != null) {
			if (root1.val == root2.val) 
				result = DoesTree1HaveTree2(root1, root2);
			
			if (!result) 
				result = hasSubTree(root1.left, root2);
			if (!result)
				result = hasSubTree(root1.right, root2);		
		}
		return result;
	}
	// 判断树 A 中以 R 为根节点的子树是不是包含和树 B 一样的结构
	public boolean DoesTree1HaveTree2(TreeNode root1, TreeNode root2) {
		if (root2 == null)
			return true;
		if (root1 == null)
			return false;
		if (root1.val != root2.val)
			return false;
		return DoesTree1HaveTree2(root1.left, root2.left) && DoesTree1HaveTree2(root1.right, root2.right);
	}
}

3、二叉树的镜像

问题描述：

请完成一个函数，输入一个二叉树，该函数输出它的镜像。

思路：

  • 前序遍历这棵树的每个结点；

  • 如果遍历到的结点有子结点，就交换它的两个子结点；

  • 当交换完所有非叶结点的左右子结点后，就得到了树的镜像。

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
public class Solution {
	public void Mirror(TreeNode root) {
		if (root == null)
			return;
		if (root.left == null && root.right == null)
			return;
		// 交换左右
		TreeNode temp = root.left;
		root.left = root.right;
		root.right = temp;
		//递归
		if (root.left != null)
			Mirror(root.left);
		if (root.right != null)
			Mirror（root.right);
	}
}

4、从上往下打印二叉树

问题描述：

从上往下打印二叉树的每个结点，同一层的结点按照从左往右的顺序打印。

思路：

实际是按层遍历二叉树。

  • 每一次打印一个结点的时候，如果该结点有子结点，则把该结点的子结点放到一个队列的末尾；

  • 接下来到队列的头部取出最早进入队列的结点，重复前面的打印操作；

  • 直到队列中所有的结点都被打印出来为止。

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;
public class Solution {
	public ArrayList<Integer> PrintFromTopToBottom(TreeNode root) {
		ArrayList<Integer> list = new ArrayList<Integer>();
		if (root == null)
			return list;
		Queue queue = new LinkedList<TreeNode>();
		queue.offer(root);
		while (!queue.isEmpty()) {
			TreeNode treenode = queue.poll();
			if (treeNode.left != null)
				queue.offer(treeNode.left);
			if (treeNode.right != null)
				queue.offer(treeNode.right);
			list.add(treeNode.val);
		} 
		return list;
	}
}

5、二叉树种和为某一值的路径

问题描述

输入一颗二叉树和一个整数，打印出二叉树中结点值的和为输入整数的所有路径。
从根结点开始妄下一直到叶结点所经过的所有结点形成一条路径。

思路：

  • 路径是从根节点出发到叶结点的。使用前序遍历。

  • 当用前序遍历的方式访问到某一结点时，我们把该结点添加到路径上，并累加该结点的值。

  • 如果该结点为叶结点，且路径中结点值的和刚好等于输入的整数，则当前路径符合要求，我们把它打印出来。

  • 如果当前结点不是叶结点，则继续访问它的子结点；

  • 当前结点结束访问后，递归函数将自动回到它的父结点。因此在函数退出之前，要在路径上删除当前结点，并减去当前结点的值。

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
import java.uril.ArrayList;
import java.util.Stack;
public class Solution {
	ArrayList<ArrayList<Integer>> listAll = new ArrayList<ArrayList<Integer>>();
	ArrayList<Integer> list = new ArrayList<Integer>();
	public ArrayList<ArrayList<Integer>> FindPath(TreeNode root, int target) {
		if (toor == null) 
			return listAll;
		list.add(root.val);
		target -= root.val;
		if (target == 0 && root.left == null && root.right == null)
			listAll.add(new ArrayList<Integer>(list));
		FindPath(root.left, target);
		FindPath(root.right, target);
		list.remove(list.size() - 1);
		return listAll;
	}
}

6、二叉树的深度

问题描述：

输入一课二叉树的根结点，求该树的深度

思路：

  • 如果一棵树只有一个结点，那么深度1；

  • 如果根结点只有左子树而没有右子树，那么深度为左子树的深度 +1；

  • 如果根结点只有右子树而没有左子树，那么深度为右子树的深度 +1；

  • 如果既有左子树又有右子树，那么深度为左右子树中的较大值 +1；

  • 递归。

代码：

1
2
3
4
5
6
7
8
9
10
11
12
import java.lang.Math;
public class Solution {
	public int TreeDepth(TreeNode root) {
		if (root == null)
			return 0;
		int left = TreeDepth(root.left);
		int right = TreeDepth(root.right);
		return Math.max(left, right) + 1;
	}
}

问题描述：

输入一颗二叉树的根结点，判断该树是不是平衡二叉树。
如果某二叉树中任意结点的左右子树的深度相差不超过1，那么它就是一棵平衡二叉树。

思路：

  • 采用后序遍历的方式遍历二叉树的每一个结点，在遍历到一个结点之前，我们就已经遍历了它的左右子树。

  • 只要在遍历每个结点的时候，记录它的深度（某一结点的深度等于它的到叶结点的路径的长度），我们就可以一边遍历一边判断每个结点是不是平衡的。

  • 注意： root == null 时，返回 true

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
public class Solution {
	private boolean isBalenced = true;
	public boolean isBalenced_Solution(TreeNode root) {
		getDepth(root);
		return isBalenced;
	}
	public int getDepth(root) {
		if (root == null)
			return 0;
		int left = getDepth(root.left);
		int right = getDepth(root.right);
		if (Math.abs(left - right) > 1)
			isBalenced = false;
		return right > left ? right + 1 : left + 1;
	}
}