Copyright © 2015 Powered by MWeb, Theme used GitHub CSS.
给定一个二叉树，它的每个结点都存放一个 0-9 的数字，每条从根到叶子节点的路径都代表一个数字。
例如，从根到叶子节点路径 \(1->2->3\) 代表数字 \(123\)。
计算从根到叶子节点生成的所有数字之和。
说明: 叶子节点是指没有子节点的节点。
示例 1:
输入: \([1,2,3]\)
1
/ \
2 3
输出: 25
解释:
从根到叶子节点路径 \(1->2\) 代表数字 \(12\).
从根到叶子节点路径 \(1->3\) 代表数字 \(13\).
因此，数字总和 = \(12 + 13 = 25\).
示例 2:
输入:\([4,9,0,5,1]\)
4
/ \
9 0
/ \
5 1
输出: \(1026\)
解释:
从根到叶子节点路径 \(4->9->5\) 代表数字 \(495\).
从根到叶子节点路径 \(4->9->1\) 代表数字 \(491\).
从根到叶子节点路径 \(4->0\) 代表数字 \(40\).
因此，数字总和 = \(495 + 491 + 40 = 1026\).
整体难度不大，使用深度优先搜索算法递归即可
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
private int result = 0;
public int sumNumbers(TreeNode root) {
dfs(root,0);
return result;
}
private void dfs(TreeNode root, int curr) {
if (root == null) {
return;
}
//需要注意的是这里要乘10再加。
curr = curr *10 + root.val;
if(root.left ==null && root.right == null) {
result += curr;
return;
}
//递归左子树
bfs(root.left, curr);
//递归右子树
bfs(root.right,curr);
}
}
给定一个二叉树，返回它的中序 遍历。
示例:
输入: \([1,null,2,3]\)
1
\
2
/
3
输出: \([1,3,2]\)
进阶: 递归算法很简单，你可以通过迭代算法完成吗？
经典的算法题，没什么可说的。
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
public List<Integer> inorderTraversal(TreeNode root) {
List<Integer> result = new LinkedList<>();
mid(root, result);
return result;
}
private void mid(TreeNode root, List<Integer> result) {
if (root ==null) {
return;
}
//先递归左子树
mid(root.left,result);
//递归完成后加入本节点
result.add(root.val);
//再递归右子树
mid(root.right, result);
}
}
构建一个栈，只要有左子树就一直压栈，直到左子树为空，出栈后将结果加入到result，然后将当前指针指向当前节点的右子树，进行下一轮压栈处理。
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
public List<Integer> inorderTraversal(TreeNode root) {
List<Integer> result = new LinkedList<>();
Stack<TreeNode> stack = new Stack<>();
while (root != null || !stack.empty()) {
//左子树一直压栈
while(root != null) {
stack.push(root);
root = root.left;
}
//出栈
root = stack.pop();
result.add(root.val);
//切换到右子树进行下一轮
root = root.right;
}
return result;
}
}
给定一个二叉树，返回它的 前序 遍历。
示例:
输入: \([1,null,2,3]\)
1
\
2
/
3
输出: \([1,2,3]\)
进阶: 递归算法很简单，你可以通过迭代算法完成吗？
没什么可说的。直接上代码吧。
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
private List<Integer> result = new LinkedList<>();
public List<Integer> preorderTraversal(TreeNode root) {
if (root == null) {
return result;
}
preorder(root);
return result;
}
public void preorder(TreeNode root) {
if (root == null) {
return;
}
//先将root.val加入result
result.add(root.val);
//递归左子树
preorder(root.left);
//递归右子树
preorder(root.right);
}
}
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
private List<Integer> result = new LinkedList<>();
public List<Integer> preorderTraversal(TreeNode root) {
if (root == null) {
return result;
}
Stack<TreeNode> stack = new Stack<>();
stack.push(root);
while (!stack.isEmpty()) {
TreeNode node = stack.pop();
result.add(node.val);
//需要注意这里right要先压栈 其他的基本无压力。
if (node.right !=null) {
stack.push(node.right);
}
if (node.left !=null) {
stack.push(node.left);
}
}
return result;
}
}
给定一个 \(N\) 叉树，返回其节点值的前序遍历。
例如，给定一个 \(3叉树\) :
返回其前序遍历: \([1,3,5,6,2,4]\)。
说明: 递归法很简单，你可以使用迭代法完成此题吗?
如果忽略说明的话，使用递归确实非常简单。与二叉树的前序遍历一样，唯一需要注意的一点是儿子是个list。递归转迭代也只是用栈来缓存
下面给出递归与迭代的不同代码
递归方式
/*
// 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 {
private List<Integer> result = new LinkedList<>();
public List<Integer> preorder(Node root) {
if (root == null) {
return result;
}
dfs(root);
return result;
}
private void dfs(Node root) {
if (root == null) {
return;
}
result.add(root.val);
//唯一需要注意的就是这里的对儿子的处理
if (root.children !=null) {
for(Node node:root.children) {
dfs(node);
}
}
}
}
迭代方式
/*
// 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 {
private List<Integer> result = new LinkedList<>();
public List<Integer> preorder(Node root) {
if (root == null) {
return result;
}
//使用栈来存储
Stack<Node> stack = new Stack<>();
stack.push(root);
while (!stack.isEmpty()) {
Node node = stack.pop();
result.add(node.val);
if (node.children !=null) {
List<Node> children = node.children;
//这里需要注意的一点是，压栈的顺序，要从最右开始压
for(int i=children.size() - 1;i >= 0;i--){
stack.push(children.get(i));
}
}
}
return result;
}
}
给定一个二叉树，判断它是否是高度平衡的二叉树。
本题中，一棵高度平衡二叉树定义为：
一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过1。
示例 1:
给定二叉树\([3,9,20,null,null,15,7]\)
3
/ \
9 20
/ \
15 7
返回\(true\)
示例 2:
给定二叉树 \([1,2,2,3,3,null,null,4,4]\)
1
/ \
2 2
/ \
3 3
/ \
4 4
返回\(false\)
深度优先搜索，首先获取左右子树的深度，判断相差是否小于1，然后递归左右子树即可，需要注意的一点是获取左右子树深度的时候需要+1
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
public boolean isBalanced(TreeNode root) {
if(root == null) {
return true;
}
//获取左子树的深度
int left = dfs(root.left);
//获取右子树的深度
int right = dfs(root.right);
//判断左右子树深度差 递归调用左右子树。
return Math.abs(left-right) <=1 && isBalanced(root.left) && isBalanced(root.right);
}
//获取树的深度
private int dfs(TreeNode root) {
if(root == null) {
return 0;
}
int left = dfs(root.left);
int right = dfs(root.right);
//左右深度+1的最大值。
return Math.max(left, right) + 1;
}
}
给定一个二叉树，找到最长的路径，这个路径中的每个节点具有相同值。 这条路径可以经过也可以不经过根节点。
**注意：**两个节点之间的路径长度由它们之间的边数表示。
示例 1:
输入:
5
/ \
4 5
/ \ \
1 1 5
输出 \(2\)
示例 2:
输入:
1
/ \
4 5
/ \ \
4 4 5
输出: \(2\)
注意: 给定的二叉树不超过\(10000\)个结点。 树的高度不超过\(1000\)。
基本想法就是深度优先遍历。遍历时，判断左右儿子的值与自己的值是否相等，相等则result++，否则置为0即可。没有什么难度。
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
private int result = 0;
public int longestUnivaluePath(TreeNode root) {
if (root != null) {
dfs(root);
}
return result;
}
private int dfs(TreeNode root) {
if (root ==null) {
return 0;
}
//计算左子树的同值路径
int left = dfs(root.left);
//判断左儿子与自己的值是否相等，相等则++ 否则置为0
if (root.left == null || root.val !=root.left.val) {
left = 0;
} else {
left ++;
}
//计算右子树的同值路径
int right = dfs(root.right);
//同左儿子的判断
if (root.right == null || root.val !=root.right.val) {
right = 0;
} else {
right ++;
}
//需要注意的是这里的max为left+right与result的判断。
result = Math.max(left + right,result);
return Math.max(left, right);
}
}
给定一棵二叉树，你需要计算它的直径长度。一棵二叉树的直径长度是任意两个结点路径长度中的最大值。这条路径可能穿过根结点。
示例 :
给定二叉树
digraph G {
{
node [margin=0 width=0.1 shape=circle style=filled]
1 -> 2 [arrowhead=none]
1 -> 3 [arrowhead=none]
2 -> 4 [arrowhead=none]
2 -> 5 [arrowhead=none]
}
}
返回\(3\),它的长度是路径 \([4,2,1,3]\) 或者 \([5,2,1,3]\)。
**注意：**两结点之间的路径长度是以它们之间边的数目表示。
此题是二叉树深度搜索的扩展，考虑设置一个全局变量result，每次递归时判断一次左子树深度+右子树深度 是否大于result，如果大于，那么将result替换成和，递归完成时，返回result即可。
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
private int result = 0;
public int diameterOfBinaryTree(TreeNode root) {
// 深度优先遍历+判断一次result大小即可。
dfs(root);
return result;
}
private int dfs(TreeNode root) {
if (root == null) {
return 0;
}
//递归左子树
int right = dfs(root.right);
//递归右子树
int left = dfs(root.left);
//左子树深度+右子树深度就是走过当前节点的直径长度
if (left + right > result) {
result = left + right;
}
//返回当前节点深度+1.递归到上一层参与计算
return Math.max(left, right) + 1;
}
}
Copyright © 2015 Powered by MWeb, Theme used GitHub CSS.