java二叉树与递归算法
public class Solution {
// Definition for a binary tree node.
public class TreeNode {
int val;
TreeNode left;
TreeNode right;
TreeNode(int x) { val = x; }
}
public int maxDepth(TreeNode root) {
//递归终止的条件，节点为空递归就应该停止，如果没有递归终止条件不停的往下执行会栈溢出
if(root == null)
return 0;
//递归的过程，描述算法逻辑
return 1 + Math.max(maxDepth(root.left), maxDepth(root.right));
}
}
import java.util.LinkedList;
public class Solution {
// Definition for a binary tree node.
public class TreeNode {
int val;
TreeNode left;
TreeNode right;
TreeNode(int x) { val = x; }
}
public TreeNode invertTree(TreeNode root) {
//递归终止的条件，节点为空递归就应该停止，如果没有递归终止条件不停的往下执行会栈溢出
if(root == null)
return null;
//递归的过程，描述反转逻辑，现将左子树进行反转，对右子树进行反转，最后交换左右孩子两棵树的位置即可
TreeNode left = invertTree(root.left);
TreeNode right = invertTree(root.right);
root.left = right;
root.right = left;
return root;
}
}
递归的终止条件的陷阱
import java.util.LinkedList;
public class Solution {
class Solution {
// Definition for a binary tree node.
public class TreeNode {
int val;
TreeNode left;
TreeNode right;
TreeNode(int x) { val = x; }
}
public boolean hasPathSum(TreeNode root, int sum) {
if(root == null)
return false;
//递归的终止条件左右子树都为空，看剩余的值是否等于根节点的值
if(root.left == null && root.right == null)
return sum == root.val;
//如果左子树不为空的话，遍历左子树，参数为总数与左子树遍历的根节点的差值
//如果右子树不为空的话，遍历右子树，参数为总数与右子树遍历的根节点的差值
return hasPathSum(root.left, sum - root.val)
|| hasPathSum(root.right, sum - root.val);
}
}
}定义递归问题
import java.util.LinkedList;
public class Solution {
// Definition for a binary tree node.
public class TreeNode {
int val;
TreeNode left;
TreeNode right;
TreeNode(int x) { val = x; }
}
public List binaryTreePaths(TreeNode root) {
ArrayList res = new ArrayList();
if(root == null)
return res;
//终止条件左右子树都为空
if(root.left == null && root.right == null){
res.add(Integer.toString(root.val));
return res;
}
//递归遍历左子树的所有路径
List leftPaths = binaryTreePaths(root.left);
for(String s: leftPaths){
StringBuilder sb = new StringBuilder(Integer.toString(root.val));
sb.append("->");
sb.append(s);
res.add(sb.toString());
}
//递归遍历右子树的所有路径
List rightPaths = binaryTreePaths(root.right);
for(String s: rightPaths) {
StringBuilder sb = new StringBuilder(Integer.toString(root.val));
sb.append("->");
sb.append(s);
res.add(sb.toString());
}
return res;
}
}ArrayList res = new ArrayList();
ArrayList totallist = new ArrayList();
binaryTreePaths(TreeNode root,res);
//递归与广度优先的不同在于递归能够一次性的走到头，然后会自动返回到最开始第一次进行进行递归遍历的地方
//广度优先则是根据不同的层级一层一层的遍历
//递归的返回值与递归的参数保存的状态是等价的，可以用递归的参数形式来取代递归的返回值
public static void binaryTreePaths(TreeNode root,List res){
if(root == null)
return;
if(root.left == null && root.right == null){
res.add(Integer.toString(root.val));
totallist.add(res);
return;
}
res.add(Integer.toString(root.val));
res.append("->");
binaryTreePaths(root.left,res);
binaryTreePaths(root.right,res);
}复杂的递归逻辑
public class FindPath {
/// Definition for a binary tree node.
public static class TreeNode {
int val;
TreeNode left;
TreeNode right;
TreeNode(int x) { val = x; }
}
// 在以root为根节点的二叉树中,寻找和为sum的路径,返回这样的路径个数
public int pathSum(TreeNode root, int sum) {
if(root == null)
return 0;
//Node的value值不再路径中的情况，继续判断是否存在一个路径这个路径的node->left与node->right的值等于sum
return findPath(root, sum)
+ pathSum(root.left , sum)
+ pathSum(root.right , sum);
}
// 在以node为根节点的二叉树中,寻找包含node的路径,和为sum
// 返回这样的路径个数
private int findPath(TreeNode node, int num){
if(node == null)
return 0;
int res = 0;
if(node.val == num)
res += 1;
//构成一个路径，这个路径最终的路径加上node的值等于sum，Node的节点一定在路径中
res += findPath(node.left , num - node.val);
res += findPath(node.right , num - node.val);
return res;
}
public static void main(String[] args) {
// 手动创建Leetcode题页上的测试用例。
// 当然, 有更好的更智能的创建二叉树的方式, 有兴趣的同学可以自行研究编写程序:)
/*****************
* 测试用例:
*
* 10
* / \
* 5 -3
* / \ \
* 3 2 11
* / \ \
* 3 -2 1
*****************/
TreeNode node1 = new TreeNode(3);
TreeNode node2 = new TreeNode(-2);
TreeNode node3 = new TreeNode(3);
node3.left = node1;
node3.right = node2;
TreeNode node4 = new TreeNode(1);
TreeNode node5 = new TreeNode(2);
node5.right = node4;
TreeNode node6 = new TreeNode(5);
node6.left = node3;
node6.right = node5;
TreeNode node7 = new TreeNode(11);
TreeNode node8 = new TreeNode(-3);
node8.right = node7;
TreeNode node9 = new TreeNode(10);
node9.left = node6;
node9.right = node8;
System.out.println((new Solution()).pathSum(node9, 8));
}
}
package jdk;
public class BinaryTree {
class Solution {
// Definition for a binary tree node.
public class TreeNode {
int val;
TreeNode left;
TreeNode right;
TreeNode(int x) { val = x; }
}
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
if(p == null || q == null)
throw new IllegalArgumentException("p or q can not be null.");
if(root == null)
return null;
//递归结构如果p和q都小于根节点root的值，最近的公共祖先一定不为root，在左子树中继续递归寻找
if(p.val < root.val && q.val < root.val)
return lowestCommonAncestor(root.left, p, q);
//递归结构如果p和q都大于根节点root的值，最近的公共祖先一定不为root，在右子树中继续递归寻找
if(p.val > root.val && q.val > root.val)
return lowestCommonAncestor(root.right, p, q);
assert p.val == root.val || q.val == root.val
|| (root.val - p.val) * (root.val - q.val) < 0;
return root;
}
}
}
