对称二叉树
解法一
递归
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]; } }
