1.合并二叉树
要求：
给定两个二叉树，想象当你将它们中的一个覆盖到另一个上时，两个二叉树的一些节点便会重叠。
你需要将他们合并为一个新的二叉树。合并的规则是如果两个节点重叠，那么将他们的值相加作为节点合并后的新值，否则不为 NULL 的节点将直接作为新二叉树的节点。
示例 :
输入:
Tree 1 Tree 2
1 2
/ \ / \
3 2 1 3
/ \ \
5 4 7
输出:
合并后的树:
3
/ \
4 5
/ \ \
5 4 7
注意: 合并必须从两个树的根节点开始。
//1.递归
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
public class Solution {
public TreeNode mergeTrees(TreeNode t1, TreeNode t2) {
if (t1 == null)
return t2;
if (t2 == null)
return t1;
t1.val += t2.val;
t1.left = mergeTrees(t1.left, t2.left);
t1.right = mergeTrees(t1.right, t2.right);
return t1;
}
}
//2.迭代法
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
public class Solution {
public TreeNode mergeTrees(TreeNode t1, TreeNode t2) {
if (t1 == null)
return t2;
Stack < TreeNode[] > stack = new Stack < > ();
stack.push(new TreeNode[] {t1, t2});
while (!stack.isEmpty()) {
TreeNode[] t = stack.pop();
if (t[0] == null || t[1] == null) {
continue;
}
t[0].val += t[1].val;
if (t[0].left == null) {
t[0].left = t[1].left;
} else {
stack.push(new TreeNode[] {t[0].left, t[1].left});
}
if (t[0].right == null) {
t[0].right = t[1].right;
} else {
stack.push(new TreeNode[] {t[0].right, t[1].right});
}
}
return t1;
}
}
2.翻转二叉树
要求：
翻转一棵二叉树。
示例：
输入：
4
/ \
2 7
/ \ / \
1 3 6 9
输出：
4
/ \
7 2
/ \ / \
9 6 3 1
//1.递归
public TreeNode invertTree(TreeNode root) {
if (root == null) {
return null;
}
TreeNode right = invertTree(root.right);
TreeNode left = invertTree(root.left);
root.left = right;
root.right = left;
return root;
}
//2.迭代
public TreeNode invertTree(TreeNode root) {
if (root == null) return null;
Queue<TreeNode> queue = new LinkedList<TreeNode>();
queue.add(root);
while (!queue.isEmpty()) {
TreeNode current = queue.poll();
TreeNode temp = current.left;
current.left = current.right;
current.right = temp;
if (current.left != null) queue.add(current.left);
if (current.right != null) queue.add(current.right);
}
return root;
}
3.判断二叉树是不是镜像对称
要求：
给定一个二叉树，检查它是否是镜像对称的。
示例：
二叉树 [1,2,2,3,4,4,3] 是对称的。
1
/ \
2 2
/ \ / \
3 4 4 3
但是下面这个 [1,2,2,null,3,null,3] 则不是镜像对称的:
1
/ \
2 2
\ \
3 3
// 1.递归
public boolean isSymmetric(TreeNode root) {
return isMirror(root, root);
}
public boolean isMirror(TreeNode t1, TreeNode t2) {
if (t1 == null && t2 == null) return true;
if (t1 == null || t2 == null) return false;
return (t1.val == t2.val)
&& isMirror(t1.right, t2.left)
&& isMirror(t1.left, t2.right);
}
//2.迭代
public boolean isSymmetric(TreeNode root) {
Queue<TreeNode> q = new LinkedList<>();
q.add(root);
q.add(root);
while (!q.isEmpty()) {
TreeNode t1 = q.poll();
TreeNode t2 = q.poll();
if (t1 == null && t2 == null) continue;
if (t1 == null || t2 == null) return false;
if (t1.val != t2.val) return false;
q.add(t1.left);
q.add(t2.right);
q.add(t1.right);
q.add(t2.left);
}
return true;
}
4.二叉树的最大深度
要求：
二叉树的深度为根节点到最远叶子节点的最长路径上的节点数。
示例：
给定二叉树 [3,9,20,null,null,15,7]，
3
/ \
9 20
/ \
15 7
返回它的最大深度 3
//1. 递归
public int maxDepth(TreeNode root) {
if (root == null) {
return 0;
}
return 1 + Math.max(maxDepth(root.left), maxDepth(root.right));
}
//2.迭代
public int maxDepth(TreeNode root) {
if(root == null) {
return 0;
}
Queue<TreeNode> queue = new LinkedList<>();
queue.offer(root);
int count = 0;
while(!queue.isEmpty()) {
int size = queue.size();
while(size-- > 0) {
TreeNode node = queue.poll();
if(node.left != null) {
queue.offer(node.left);
}
if(node.right != null) {
queue.offer(node.right);
}
}
count++;
}
return count;
}
5.二叉树的层次遍历
5.1 二叉树的层次遍历（常规输出）
示例：
给定二叉树: [3,9,20,null,null,15,7],
3
/ \
9 20
/ \
15 7
返回其层次遍历结果：
[3,9,20,15,7]
//1.递归
public void levelTraversal(TreeNode root){
}
//2.迭代
public static void levelTraversal(TreeNode root){
if(root == null) {
return;
}
Queue<TreeNode> queue = new LinkedList<>(); // 对列保存树节点
queue.add(root);
while (!queue.isEmpty()) {
TreeNode temp = queue.poll();
System.out.print(temp.val + "->");
if (temp.left != null) { // 添加左右子节点到对列
queue.add(temp.left);
}
if (temp.right != null) {
queue.add(temp.right);
}
}
}
5.2.二叉树的层次遍历（变种输出）
要求：
给定一个二叉树，返回其按层次遍历的节点值。 （即逐层地，从左到右访问所有节点）。
示例：
给定二叉树: [3,9,20,null,null,15,7],
3
/ \
9 20
/ \
15 7
返回其层次遍历结果：
[
[3],
[9,20],
[15,7]
]
public class Solution {
public List<List<Integer>> levelOrder(TreeNode root) {
Queue<TreeNode> queue = new LinkedList<TreeNode>();
List<List<Integer>> wrapList = new LinkedList<List<Integer>>();
if(root == null) return wrapList;
queue.offer(root);
while(!queue.isEmpty()){
int levelNum = queue.size();
List<Integer> subList = new LinkedList<Integer>();
for(int i=0; i<levelNum; i++) {
if(queue.peek().left != null) queue.offer(queue.peek().left);
if(queue.peek().right != null) queue.offer(queue.peek().right);
subList.add(queue.poll().val);
}
wrapList.add(subList);
}
return wrapList;
}
}
6.相同的树
要求：
给定两个二叉树，编写一个函数来检验它们是否相同。
如果两个树在结构上相同，并且节点具有相同的值，则认为它们是相同的。
示例 1:
输入: 1 1
/ \ / \
2 3 2 3
[1,2,3], [1,2,3]
输出: true
示例 2:
输入: 1 1
/ \ / \
2 1 1 2
[1,2,1], [1,1,2]
输出: false
//1.递归
public boolean isSameTree(TreeNode p, TreeNode q) {
if(p==null && q==null) return true;
if(p==null || q==null) return false;
return (p.val==q.val) && isSameTree(p.left,q.left) && isSameTree(p.right,q.right);
}
//2.迭代
public boolean isSameTree(TreeNode p, TreeNode q) {
if (p == null && q == null) return true;
if(p==null || q==null) return false;
Queue<TreeNode> stackP = new LinkedList<>();
Queue<TreeNode> stackQ = new LinkedList<>();
stackP.add(p);
stackQ.add(q);
while (!stackP.isEmpty() && !stackQ.isEmpty()) {
TreeNode tmpP = stackP.poll();
TreeNode tmpQ = stackQ.poll();
if (tmpP.val != tmpQ.val) return false;
if (tmpP.left != null && tmpQ.left != null) {
stackP.add(tmpP.left);
stackQ.add(tmpQ.left);
} else if (tmpP.left == null && tmpQ.left == null) {
} else {
return false;
}
if (tmpP.right != null && tmpQ.right != null) {
stackP.add(tmpP.right);
stackQ.add(tmpQ.right);
} else if (tmpP.right == null && tmpQ.right == null) {
} else {
return false;
}
}
if (!stackP.isEmpty() || !stackQ.isEmpty()) return false;
return true;
}
7.平衡二叉树
要求：
给定一个二叉树，判断它是否是平衡的二叉树。
性质：
1.它是一 棵空树或它的左右两个子树的高度差的绝对值不超过1
2.并且左右两个子树都是一棵平衡二叉树
- 1.递归（时间复杂度O(n^2)，先序遍历）
二叉树中的很多结点遍历了多次；
求解根的的高度时，需要先求解根的左子树高度和右子树高度，这就遍历了整棵左子树中的结点和右子树中的结点。而求解以根的左孩子为根的子树的高度时，又需要遍历它(根的左孩子)的左子树和右子树。这样，相当于很多结点的高度重复计算了。
public boolean isBalanced(TreeNode root) {
if(null == root) return true;
int left = depth(root.left);
int right = depth(root.right);
return Math.abs(left - right) <= 1 && isBalanced(root.left) && isBalanced(root.right);
}
public int depth(TreeNode root){
if(null == root) return 0;
return Math.max(depth(root.left), depth(root.right)) + 1;
}
- 2.递归（时间复杂度O(n),后序遍历））
先知道某结点左右子树的高度，如果左右子树的高度都不满足平衡二叉树(二者高度相减大于1)，那么都不需要再去求解该结点的高度了。
public boolean isBalanced(TreeNode root) {
return dfsHeight (root) != -1;
}
public int dfsHeight (TreeNode root){
if (root == null) return 0;
int leftHeight = dfsHeight (root.left);
if(-1 == leftHeight) return -1;
int rightHeight = dfsHeight(root.right);
if(-1 == rightHeight) return -1;
if(Math.abs(leftHeight - rightHeight) > 1) return -1;
return Math.max(leftHeight,rightHeight) + 1;
}
网友评论