👨💻个人主页: 才疏学浅的木子 🙇♂️ 本人也在学习阶段如若发现问题,请告知非常感谢 🙇♂️ 📒 本文来自专栏: 算法 🌈 算法类型:Hot100题 🌈
解法一
递归
class Solution {
public boolean isSymmetric(TreeNode root) {
if(root == null) return true;
return fun(root.left,root.right);
}
public boolean fun(TreeNode left,TreeNode right){
if(left == null && right != null) return false;
if(right == null && left != null) return false;
if(left == null && right == null) return true;
if(right.val != left.val) return false;
return fun(left.left,right.right)&&fun(left.right,right.left);
}
}
解法一
递归 前序遍历是 根 左 右 中序遍历是 左 根 右 我们可以根据前序遍历将中序遍历分为左子树,根,右子树 这又变成根据前序+中序建立一个二叉树
class Solution {
HashMap<Integer,Integer> map = new HashMap<>();
public TreeNode buildTree(int[] preorder, int[] inorder) {
for(int i = 0;i < inorder.length;i++){
map.put(inorder[i],i);
}
return dfs(preorder,inorder,0,preorder.length-1,0,inorder.length-1);
}
public TreeNode dfs(int [] preorder,int []inorder,int left1,int right1,int left2,int right2){
if(left1 > right1 && left2 > right2) {
return null;
}
TreeNode node = new TreeNode(preorder[left1]);
int i = map.get(preorder[left1]);
node.left = dfs(preorder,inorder,left1+1,left1+i-left2,left2,i-1);
node.right = dfs(preorder,inorder,left1+i-left2+1,right1,i+1,right2);
return node;
}
}
解法一
动态规划 1~n F(i,n)表示以i为根节点,长度为n的不同树的个数 dp[n] 表示长度为n的不同树的个数 dp[n] = F(1,n)+f(2,n)+…+f(n,n) f(i,n) = dp[i-1]*dp[n-i] dp[n] = dp(0)*dp[n-1]+dp[1]*dp[n-2]…+dp[n-1]*dp[0]
class Solution {
public int numTrees(int n) {
int dp[] = new int[n+1];
dp[0] = 1;
dp[1] = 1;
for(int i = 2;i <= n; i++){
for(int j = 1;j <= i;j++){
dp[i] += dp[j-1]*dp[i-j];
}
}
return dp[n];
}
}