合并二叉树

给定两个二叉树,想象当你将它们中的一个覆盖到另一个上时,两个二叉树的一些节点便会重叠。
你需要将他们合并为一个新的二叉树。合并的规则是如果两个节点重叠,那么将他们的值相加作为节点合并后的新值,否则不为 NULL 的节点将直接作为新二叉树的节点。

示例 1:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
输入: 
Tree 1 Tree 2
1 2
/ \ / \
3 2 1 3
/ \ \
5 4 7
输出:
合并后的树:
3
/ \
4 5
/ \ \
5 4 7

思路

递归算法,每棵树都由子树构成,根节点融合可以通过递归拆分成子树进行。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
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;
}
}

二叉树最大深度

给定一个二叉树,找出其最大深度。
二叉树的深度为根节点到最远叶子节点的最长路径上的节点数。

说明: 叶子节点是指没有子节点的节点。

示例:
给定二叉树 [3,9,20,null,null,15,7]

1
2
3
4
5
 3
/ \
9 20
/ \
15 7

返回它的最大深度 3 。

思路

同上,树划分成两棵树,递归求解。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
public int maxDepth(TreeNode root) {
if(root==null)
return 0;
return Math.max(maxDepth(root.left), maxDepth(root.right))+1;
}
}

题目链接

N叉树的最大深度

给定一个 N 叉树,找到其最大深度。

最大深度是指从根节点到最远叶子节点的最长路径上的节点总数。

例如,给定一个 3叉树 :

我们应返回其最大深度,3。

说明:

树的深度不会超过 1000。
树的节点总不会超过 5000。

思路+代码

类比二叉树最大深度,迭代求解。

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
/*
// Definition for a Node.
class Node {
public int val;
public List<Node> children;

public Node() {}

public Node(int _val,List<Node> _children) {
val = _val;
children = _children;
}
};
*/
class Solution {
public int maxDepth(Node root) {
if(root==null)
return 0;
int depth = 0;
for(int i=0; i<root.children.size(); i++){
depth = Math.max(maxDepth(root.children.get(i)),depth);
}
return depth+1;
}
}

翻转二叉树

翻转一棵二叉树。

示例:
输入:

1
2
3
4
5
     4
/ \
2 7
/ \ / \
1 3 6 9

输出:

1
2
3
4
5
     4
/ \
7 2
/ \ / \
9 6 3 1

备注:

这个问题是受到 Max Howell 的 原问题 启发的 :

谷歌:我们90%的工程师使用您编写的软件(Homebrew),但是您却无法在面试时在白板上写出翻转二叉树这道题,这太糟糕了。

思路

so easy! 递归完事了。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
public TreeNode invertTree(TreeNode root) {
if(root==null) return null;

TreeNode obj = root.left;
root.left = root.right;
root.right = obj;
invertTree(root.right);
invertTree(root.left);

return root;
}
}