leetcode上二叉树和递归 java
二叉树天然的递归结构
104. 二叉树的最大深度
给定一个二叉树，找出其最大深度。
二叉树的深度为根节点到最远叶子节点的最长路径上的节点数。
说明: 叶子节点是指没有子节点的节点。
示例：
给定二叉树 [3,9,20,null,null,15,7]，
3
/ \
9 20
... / \
15 7
返回它的最大深度 3 。
/**
* 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;
int l=maxDepth(root.left);
int r=maxDepth(root.right);
if(l<r)
return r+1;
else return l+1;
}
}
接下来的这道题有一点故事
翻转一棵二叉树。
示例：
输入：
4
/ \
2 7
/ \ / \
1 3 6 9
输出：
4
/ \
7 2
/ \ / \
9 6 3 1
备注:
这个问题是受到 Max Howell 的 原问题 启发的 ：
谷歌：我们90％的工程师使用您编写的软件(Homebrew)，但是您却无法在面试时在白板上写出翻转二叉树这道题，这太糟糕了。
/**
* 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 left=invertTree(root.left);
TreeNode right= invertTree(root.right);
root.right=left;
root.left=right;
return root;
}
}
注意递归的终止条件
来自leetcode112
给定一个二叉树和一个目标和，判断该树中是否存在根节点到叶子节点的路径，这条路径上所有节点值相加等于目标和。
说明: 叶子节点是指没有子节点的节点。
示例:
给定如下二叉树，以及目标和 sum = 22，
5
/ \
4 8
/ / \
11 13 4
/ \ \
7 2 1
返回 true, 因为存在目标和为 22 的根节点到叶子节点的路径 5->4->11->2。
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
public boolean hasPathSum(TreeNode root, int sum) {
if(root==null)
return false;
if(root.left==null&&root.right==null)
return root.val==sum;
if(hasPathSum(root.left,sum-root.val))
return true;
if(hasPathSum(root.right,sum-root.val))
return true;
return false;
}
}
leetcode257
给定一个二叉树，返回所有从根节点到叶子节点的路径。
说明: 叶子节点是指没有子节点的节点。
输入:
1
/ \
2 3
\
5
输出: ["1->2->5", "1->3"]
解释: 所有根节点到叶子节点的路径为: 1->2->5, 1->3
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
public List<String> binaryTreePaths(TreeNode root) {
List<String> res=new ArrayList<String>();
if(root==null)
return res;
if(root.left==null&&root.right==null)
{res.add(Integer.toString(root.val));
return res;}
List<String> l=new ArrayList<String>();
List<String> r=new ArrayList<String>();
l=binaryTreePaths(root.left);
r=binaryTreePaths(root.right);
for(int i=0;i<l.size();i++)
res.add(Integer.toString(root.val)+"->"+l.get(i));
for(int i=0;i<r.size();i++)
res.add(Integer.toString(root.val)+"->"+r.get(i));
return res;
}
}
给定一个二叉树，它的每个结点都存放着一个整数值。
找出路径和等于给定数值的路径总数。
路径不需要从根节点开始，也不需要在叶子节点结束，但是路径方向必须是向下的（只能从父节点到子节点）。
二叉树不超过1000个节点，且节点数值范围是 [-1000000,1000000] 的整数。
示例：
root = [10,5,-3,3,2,null,11,3,-2,null,1], sum = 8
返回 3。和等于 8 的路径有:
1. 5 -> 3
2. 5 -> 2 -> 1
3. -3 -> 11
遍历每个节点。 关键点：递归
计算以当前节点为路径终点的所有路径和。 关键点：用一个数组保存从根节点到当前节点路径
public int pathSum(TreeNode root, int sum) {
return pathSum(root, sum, new int[1000], 0);
}
public int pathSum(TreeNode root, int sum, int[] array/*保存路径*/, int p/*指向路径终点*/) {
if (root == null) {
return 0;
}
int tmp = root.val;
int n = root.val == sum ? 1 : 0;
for (int i = p - 1; i >= 0; i--) {
tmp += array[i];
if (tmp == sum) {
n++;
}
}
array[p] = root.val;
int n1 = pathSum(root.left, sum, array, p + 1);
int n2 = pathSum(root.right, sum, array, p + 1);
return n + n1 + n2;
}
此题答案来自于题解作者：xiao-chao-wang-yi-lang
链接：https://leetcode-cn.com/problems/path-sum-iii/solution/javajie-fa-shi-jian-100-kong-jian-93-by-xiao-chao-/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
二分搜索树的问题
难度简单240 收藏 分享 切换为英文 关注 反馈
给定一个二叉搜索树, 找到该树中两个指定节点的最近公共祖先。
百度百科中最近公共祖先的定义为：“对于有根树 T 的两个结点 p、q，最近公共祖先表示为一个结点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。”
例如，给定如下二叉搜索树: root = [6,2,8,0,4,7,9,null,null,3,5]
image
示例 1:
输入: root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 8
输出: 6
解释: 节点 2 和节点 8 的最近公共祖先是 6。
示例 2:
输入: root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 4
输出: 2
解释: 节点 2 和节点 4 的最近公共祖先是 2, 因为根据定义最近公共祖先节点可以为节点本身。
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
//边界检查
if(root==null)
return null;
if(p.val<root.val && q.val<root.val)
return lowestCommonAncestor(root.left,p,q);
if(p.val>root.val && q.val>root.val)
return lowestCommonAncestor(root.right,p,q);
return root;
}
}
