| 章节 | 典型题目 | 相关题目 | 更多扩展练习 | 难题推荐 |
|---|---|---|---|---|
| 5-1 二叉树天然的递归结构 | 104 | 111 | ||
| 5-2 一个简单的二叉树问题引发的血案 Invert Binary Tree | 226 | 100 101 222 110 | ||
| 5-3 注意递归的终止条件 Path Sum | 112 | 111 404 | ||
| 5-4 定义递归问题 Binary Tree Path | 257 | 113 129 | ||
| 5-5 稍复杂的递归逻辑 Path Sum III | 437 | [无] | 785 | |
| 5-6 二分搜索树中的问题 Lowest Common Ancestor of a Binary Search Tree | 235 | 783 98 450 108 230 236 | 530 99 | |
| 补充1 更多二叉树的问题 | [无] | [无] | 109 105 106 889 173* 863 865 872 894 897 95 | 87 |
| 补充2 二叉树相关的所有操作 | [无] | [无] | [无] | [无] |
| 补充3 二分搜索树的基本操作 | [无] | [无] | [无] | [无] |
104 Maximum Depth of Binary Tree
- 问题：
求一棵二叉树的最大深度。
- 解题：
public int maxDepth(TreeNode root) {
if(root==null){
return 0;
}
return Math.max(maxDepth(root.left),maxDepth(root.right))+1;
}111 Minimum Depth of Binary Tree
public int minDepth(TreeNode root) {
if(root==null) {
return 0;
}
/**
* 针对
* 1
* \
* 2
* 的情况
*/
if(root.left==null){
return minDepth(root.right)+1;
}
/**
* 针对
* 1
* /
* 2
* 的情况
*/
if(root.right==null){
return minDepth(root.left)+1;
}
return Math.min(minDepth(root.left),minDepth(root.right))+1;
}- 问题：
反转一棵二叉树。
- 示例：
- 解题：
public TreeNode invertTree(TreeNode root) {
if(root==null){
return null;
}
invertTree(root.left);
invertTree(root.right);
//交换root的左右节点
TreeNode tmp=root.left;
root.left=root.right;
root.right=tmp;
return root;
}public boolean isSameTree(TreeNode p, TreeNode q) {
if(p==null && q==null){
return true;
}
if(p==null && q!=null){
return false;
}
if(p!=null && q==null){
return false;
}
//注意p.q是对象，比较的是节点的值
if(p.val!=q.val){
return false;
}
return isSameTree(p.left,q.left) && isSameTree(p.right,q.right);
}public boolean isSymmetric(TreeNode root) {
if(root==null){
return true;
}
return isSymmetric(root.left,root.right);
}
//判断两棵树是否对称
private boolean isSymmetric(TreeNode p,TreeNode q){
if(p==null && q==null){
return true;
}
if(p==null && q!=null){
return false;
}
if(p!=null && q==null){
return false;
}
//注意p.q是对象，比较的是节点的值
if(p.val!=q.val){
return false;
}
return isSymmetric(p.left,q.right) && isSymmetric(p.right,q.left);
}/**
* 思路：
* 如果用常规的解法一个个遍历，就是O(n)时间复杂度 ，会不通过。
* 因为是完全二叉树，满二叉树有一个性质是节点数等于2^h-1,h为高度，
* 所以可以这样判断节点的左右高度是不是一样，如果是一样说明是满二叉树，
*/
public int countNodes(TreeNode root) {
//空树
if(root==null){
return 0;
}
//只有一个节点
if(root.left==null && root.right==null){
return 1;
}
int l=getLeftHeight(root);
int r=getRightHeight(root);
if(l==r){
return (1<<r)-1;
//(1<<r)表示的是 2^r ，也就是有l层满二叉树中节点的数目是 （2^r-1）
}else{
return countNodes(root.left)+countNodes(root.right)+1;
}
}
private int getLeftHeight(TreeNode root){
int height=0;
while(root!=null){
height++;
root=root.left;
}
return height;
}
private int getRightHeight(TreeNode root){
int height=0;
while(root!=null){
height++;
root=root.right;
}
return height;
}public boolean isBalanced(TreeNode root) {
if(root==null){
return true;
}
if(root.left==null && root.right==null){
return true;
}
//获取该树的左右子树的深度
int l=getTreeDepth(root.left);
int r=getTreeDepth(root.right);
if(Math.abs(l-r)>1){
return false;
}
return isBalanced(root.left) && isBalanced(root.right);
}
//得到一棵树的深度
private int getTreeDepth(TreeNode root){
if(root==null){
return 0;
}
return Math.max(getTreeDepth(root.left),getTreeDepth(root.right))+1;
}- 问题：
- 解题：
public boolean hasPathSum(TreeNode root, int sum) {
//注意递归结束的条件
if(root==null){
//如果是一个空树，那么是不可能有路径的
return false;
}
if(root.left==null && root.right==null){
//如果根节点是叶子节点
return root.val==sum;
}
return hasPathSum(root.left,sum-root.val) || hasPathSum(root.right,sum-root.val);
}111 Minimum Depth of Binary Tree
public int minDepth(TreeNode root) {
if(root==null) {
return 0;
}
/**
* 针对
* 1
* \
* 2
* 的情况
*/
if(root.left==null){
return minDepth(root.right)+1;
}
/**
* 针对
* 1
* /
* 2
* 的情况
*/
if(root.right==null){
return minDepth(root.left)+1;
}
return Math.min(minDepth(root.left),minDepth(root.right))+1;
}public int sumOfLeftLeaves(TreeNode root) {
if(root==null){
return 0;
}
if(root.left!=null && (root.left.left==null && root.left.right==null)){
return root.left.val+sumOfLeftLeaves(root.right);
}
return sumOfLeftLeaves(root.left)+sumOfLeftLeaves(root.right);
}- 问题：
- 解题：
递归的思路：将一棵树拆成 root->左子树对应字符串 + root->右子树对应的字符串
在左子树进行相同的操作：
在右子树进行相同的操作：
public List<String> binaryTreePaths(TreeNode root) {
List<String> ret=new ArrayList<>();
if(root==null){
return ret;
}
if(root.left==null && root.right==null){
ret.add(root.val+"");
return ret;
}
List<String> leftS=binaryTreePaths(root.left);
for(String s:leftS){
ret.add(root.val+"->"+s);
}
List<String> rightS=binaryTreePaths(root.right);
for(String s:rightS){
ret.add(root.val+"->"+s);
}
return ret;
}- 解法一：
public List<List<Integer>> pathSum(TreeNode root, int sum) {
//将 findPath所得的结果转换为适当的格式返回
List<List<Integer>> res=new ArrayList<>();
List<String> ret=findPath(root,sum);
for(String str:ret){
List<Integer> tmp=new ArrayList<>();
String[] val=str.split("->");
for(String v:val){
Integer i=Integer.parseInt(v);
tmp.add(i);
}
res.add(tmp);
}
return res;
}
//找从根节点到叶子节点的路径和为sum的路径
private List<String> findPath(TreeNode root,int sum){
List<String> paths = new ArrayList<>();
if(root == null){
return paths;
}
if(root.left == null && root.right == null){
if(root.val==sum){
paths.add(root.val+"");
return paths;
}
}
List<String> leftPath=findPath(root.left,sum-root.val);
for (String path : leftPath) {
paths.add(root.val + "->" + path);
}
List<String> rightPath=findPath(root.right,sum-root.val);
for (String path : rightPath) {
paths.add(root.val + "->" + path);
}
return paths;
}- 解法二：
private List<List<Integer>> res;
public List<List<Integer>> pathSum(TreeNode root, int sum) {
res=new ArrayList<>();
if(root==null){
return res;
}
List<Integer> p=new ArrayList<>();
dfs(root,0,sum,p);
return res;
}
private void dfs(TreeNode node,int tSum, int sum,List<Integer> p){
if(node==null){
return;
}
p.add(node.val);
tSum+=node.val;
//到达叶子节点并且路径值和为sum,这说明找到了一条路径，将值存入
if(node.left==null && node.right==null){
if(tSum==sum){
res.add(new ArrayList<>(p));
}
}else{
if(node.left!=null){
dfs(node.left,tSum,sum,p);
}
if(node.right!=null){
dfs(node.right,tSum,sum,p);
}
}
p.remove(p.size()-1);
tSum-=node.val;
return;
}public int sumNumbers(TreeNode root) {
List<String> ret=findPath(root);
int sum=0;
for(String ele:ret){
Integer i=Integer.parseInt(ele);
sum+=i;
}
return sum;
}
//查找所有到叶子结点的路径
private List<String> findPath(TreeNode root){
List<String> ret=new ArrayList<>();
if(root==null){
return ret;
}
if(root.left==null && root.right==null){
ret.add(root.val+"");
return ret;
}
List<String> leftPath=findPath(root.left);
for(String path:leftPath){
ret.add(root.val+""+path);
}
List<String> rightPath=findPath(root.right);
for(String path:rightPath){
ret.add(root.val+""+path);
}
return ret;
}- 问题：
给出一棵二叉树以及一个数字sum,判断在这棵二叉树上存在多少条路径，其路径上的所有节点和为sum。
其中路径不一定要起始于根节点；终止于叶子结点。
路径可以从任意节点开始，但是只能是向下走的。
- 示例：
- 解题：
//以root为根节点的二叉树中，寻找和为sum的路径，返回这样的路径的个数
public int pathSum(TreeNode root, int sum) {
if(root==null){
return 0;
}
int res=findPath(root,sum);
res+=pathSum(root.left,sum);
res+=pathSum(root.right,sum);
return res;
}
//以node为根节点的二叉树中，寻找包含node的路径，和为sum
//返回这样的路径个数
private int findPath(TreeNode node,int sum){
if(node==null){
return 0;
}
int res=0;
if(node.val==sum){
res+=1;
}
res+=findPath(node.left,sum-node.val);
res+=findPath(node.right,sum-node.val);
return res;
}/**
* 思路：
* 首先检查该结点是否已经被检查，如果是，则看看是否能满足要求；
* 否则就给结点分组，并且采用DFS的策略对和其直接或者间接相连的所有结点进行分组。
* 整个过程中如果发现冲突就提前返回false；否则在最后返回true。
*/
private int[] checked;
public boolean isBipartite(int[][] graph) {
checked=new int[graph.length];
for(int i=0;i<checked.length;i++){
checked[i]=-1;
}
for(int i=0;i<graph.length;i++){
if(checked[i]==-1){
if(!check(graph,i,0)){
return false;
}
}
}
return true;
}
/**
* @param graph
* @param index 对应的结点下标
* @param group 分组标号，数值为0和1，group初始值为0，1-group值就变成1
* @return
*/
private boolean check(int[][] graph,int index,int group){
if(checked[index]!=-1){
//首先检查该结点是否已经被检查，如果是，则看看是否能满足要求；
return checked[index]==group;
}
checked[index]=group;
//遍历与该结点相连的其他结点
for(int next:graph[index]){
if(!check(graph,next,1-group)){
return false;
}
}
return true;
}
235 Lowest Common Ancestor of a Binary Search Tree
- 问题
- 解题：
p,q都是该二分搜索树的节点，对于p,q节点的公共祖先节点，分为3个情况：
(1) p，q值都小于node，则他们的公共祖先在node的左子树中
(2) p，q值都大于node，则他们的公共祖先在node的右子树中
(3) node在p,q之间的，则他们的公共祖先就是node
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;
}783 Minimum Distance Between BST Nodes
public int minDiffInBST(TreeNode root) {
inOrder(root);
int min=Integer.MAX_VALUE;
for(int i=0;i<inOrder.size()-1;i++){
Integer num1=inOrder.get(i);
Integer num2=inOrder.get(i+1);
min=Math.min(min,Math.abs(num1-num2));
}
return min;
}
private List<Integer> inOrder=new ArrayList<>();
private void inOrder(TreeNode root){
if(root==null){
return;
}
inOrder(root.left);
inOrder.add(root.val);
inOrder(root.right);
}98 Validate Binary Search Tree
//注意数值范围的问题，有的节点的值超过了int类型的范围
public boolean isValidBST(TreeNode root) {
return isValid(root,Long.MIN_VALUE,Long.MAX_VALUE);
}
//判断左子树最大值为leftMax,右子树最小值为rightMin的树是否是BST
public boolean isValid(TreeNode root,long leftMax,long rightMin){
if(root==null){
return true;
}
if(root.left==null && root.right==null){
return true;
}
if(root.val<=leftMax || root.val>=rightMin){
return false;
}
return isValid(root.left,leftMax,root.val) && isValid(root.right,root.val,rightMin);
}public TreeNode deleteNode(TreeNode root, int key) {
if (root == null){
return root;
}
//删除的是根结点
if(root.val==key){
//右子树为空，那么就直接删除该根节点，返回右子树
if(root.right==null){
TreeNode node=root.left;
root=node;
return root;
}else{
//右子树不为空，则将该右子树的最小值，代替根结点的值
TreeNode right=root.right;
while(right.left!=null){
right=right.left;
}
int tmp=root.val;
root.val=right.val;
right.val=tmp;
}
}
root.left=deleteNode(root.left,key);
root.right=deleteNode(root.right,key);
return root;
}108 Convert Sorted Array to Binary Search Tree
public TreeNode sortedArrayToBST(int[] nums) {
return sortedArrayToBST(nums,0,nums.length-1);
}
private TreeNode sortedArrayToBST(int[] nums,int start,int end) {
if(start>end){
return null;
}
int mid=start+(end-start)/2;
//将中间结点作为根结点，
//这样其左子树元素为[strat...mid-1]
//右子树元素为[mid+1...end]
TreeNode root=new TreeNode(nums[mid]);
if(start==end){
return root;
}
root.left=sortedArrayToBST(nums,start,mid-1);
root.right=sortedArrayToBST(nums,mid+1,end);
return root;
}230 Kth Smallest Element in a BST
private int index=0;
private TreeNode tmp;
//k是从1开始的
//k始终有效
public int kthSmallest(TreeNode root, int k) {
inOrder(root,k);
return tmp.val;
}
//利用BST树中序遍历的性质,得到第k个元素,就停止中序遍历。
public void inOrder(TreeNode root,int k){
if(root==null){
return;
}
inOrder(root.left,k);
index++;
if(index==k){
tmp=root;
return;
}
inOrder(root.right,k);
}236 Lowest Common Ancestor of a Binary Tree
// 在root中寻找p和q
// 如果p和q都在root所在的二叉树中, 则返回LCA
// 如果p和q只有一个在root所在的二叉树中, 则返回p或者q
// 如果p和q均不在root所在的二叉树中, 则返回NULL
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
if(root==null){
return null;
}
//根节点是p或者q，则就返回该根节点就可以了
if(root==p || root==q){
return root;
}
//看看root的最子树是否包含p,q
TreeNode left=lowestCommonAncestor(root.left,p,q);
TreeNode right=lowestCommonAncestor(root.right,p,q);
//p,q的最小公共祖先
//要么是root
//要么是在root的左子树
//要么是在root的右子树
if(left!=null && right!=null){
return root;
}
if(left!=null){
return left;
}
if(right!=null){
return right;
}
return null;
}109 Convert Sorted List to Binary Search Tree
- 思路一：参考108题，但是效率太低。
public TreeNode sortedListToBST(ListNode head) {
if(head==null){
return null;
}
return sortedListToBST(head,0,getLength(head)-1);
}
private TreeNode sortedListToBST(ListNode head,int start,int end){
if(start>end){
return null;
}
int mid=start+(end-start)/2;
TreeNode root=new TreeNode(getElement(head,mid));
if(start==end){
return root;
}
root.left=sortedListToBST(head,start,mid-1);
root.right=sortedListToBST(head,mid+1,end);
return root;
}
private int getLength(ListNode head){
int count=0;
ListNode cur=head;
while(cur!=null){
count++;
cur=cur.next;
}
return count;
}
//按照index获取链表中数据
private int getElement(ListNode head,int index){
int i=0;
ListNode cur=head;
while(cur!=null && i!=index){
cur=cur.next;
i++;
}
return cur.val;
}- 思路二：
private ListNode cur;
public TreeNode sortedListToBST(ListNode head) {
if (head == null) {
return null;
}
cur=head;
return buildBST(0,getLength(head)-1);
}
private TreeNode buildBST(int start,int end){
if(start>end){
return null;
}
int mid=start+(end-start)/2;
TreeNode left=buildBST(start,mid-1);
TreeNode root=new TreeNode(cur.val);
cur=cur.next;
TreeNode right=buildBST(mid+1,end);
root.left=left;
root.right=right;
return root;
}
private int getLength(ListNode head){
int count=0;
ListNode cur=head;
while(cur!=null){
count++;
cur=cur.next;
}
return count;
}105 Construct Binary Tree from Preorder and Inorder Traversal
public TreeNode buildTree(int[] preorder, int[] inorder) {
return buildTree(preorder,inorder,0,preorder.length-1,0,inorder.length-1);
}
private TreeNode buildTree(int[] preorder,int[] inorder,int preStart,int preEnd,int inStart,int inEnd){
if(preStart>preEnd || inStart>inEnd){
return null;
}
TreeNode root=new TreeNode(preorder[preStart]);
int mid=0;
for(int i=inStart;i<=inEnd;i++){
if(inorder[i]==preorder[preStart]){
mid=i;
break;
}
}
root.left=buildTree(preorder,inorder,preStart+1,preStart+(mid-inStart),inStart,mid-1);
root.right=buildTree(preorder,inorder,preStart+(mid-inStart)+1,preEnd,mid+1,inEnd);
return root;
}106 Construct Binary Tree from Inorder and Postorder Traversal
public TreeNode buildTree(int[] inorder, int[] postorder) {
return buildTree(inorder,postorder,0,inorder.length-1,0,postorder.length-1);
}
private TreeNode buildTree(int[] inorder,int[] postorder,int inStart,int inEnd,int postStart,int postEnd){
if(inStart>inEnd || postStart>postEnd){
return null;
}
TreeNode root=new TreeNode(postorder[postEnd]);
int mid=0;
for(int i=inStart;i<=inEnd;i++){
if(inorder[i]==postorder[postEnd]){
mid=i;
break;
}
}
root.left=buildTree(inorder,postorder,inStart,mid-1,postStart,postStart+(mid-inStart)-1);
root.right=buildTree(inorder,postorder,mid+1,inEnd,postStart+(mid-inStart),postEnd-1);
return root;
}889 Construct Binary Tree from Preorder and Postorder Traversal
public TreeNode constructFromPrePost(int[] pre, int[] post) {
return constructFromPrePost(pre,post,0,pre.length-1,0,post.length-1);
}
private TreeNode constructFromPrePost(int[] pre, int[] post,int preStart,int preEnd,int postStart,int postEnd){
if(preStart>preEnd || postStart>postEnd){
return null;
}
TreeNode root=new TreeNode(pre[preStart]);
if(preStart==preEnd){
return root;
}
//左子树根结点
int k;
for(k=postStart;k<postEnd;k++){
if(post[k]==pre[preStart+1]){
break;
}
}
root.left=constructFromPrePost(pre,post,preStart+1,preStart+k-postStart+1,postStart,k);
root.right=constructFromPrePost(pre,post,preStart+k-postStart+2,preEnd,k+1,postEnd-1);
return root;
}173 Binary Search Tree Iterator
/**
* 思路一：
* 就是利用BST的中序遍历性质(递归思路)
* 空间复杂度：O(n)
* 时间复杂度： next() --> O(1)
* hasNext() --> O(1)
*/
class BSTIterator {
private List<Integer> data=new ArrayList<>();
private int nextIndex;
public BSTIterator(TreeNode root) {
inOrder(root);
nextIndex=0;
}
private void inOrder(TreeNode root){
if(root==null){
return;
}
inOrder(root.left);
data.add(root.val);
inOrder(root.right);
}
/** @return the next smallest number */
public int next() {
return data.get(nextIndex++);
}
/** @return whether we have a next smallest number */
public boolean hasNext() {
return nextIndex<data.size()-1;
}
}/**
* 思路二：非递归方式
* 空间复杂度：O(h)
* 时间复杂度：next() --> O(1)
* hasNext() --> O(h)
*/
class BSTIterator{
private Stack<TreeNode> myStack;
public BSTIterator(TreeNode root) {
myStack=new Stack<>();
TreeNode node = root;
while(node != null){
myStack.push(node);
node = node.left;
}
}
/** @return the next smallest number */
public int next() {
assert(hasNext());
TreeNode retNode = myStack.pop();
TreeNode node = retNode.right;
while(node != null){
myStack.push(node);
node = node.left;
}
return retNode.val;
}
/** @return whether we have a next smallest number */
public boolean hasNext() {
return !myStack.isEmpty();
}
}863 All Nodes Distance K in Binary Tree
/**
* 解题思路：先从根dfs一遍，将树变成图。之后从要求的点bfs即可。
*/
//使用集合数组存储图
private Vector<Integer>[] G;
//用于判断图中某一个结点，是否被访问
private boolean[] isVisited;
//通过dfs操作将该二叉树，转化为一个无向图
private void dfs(TreeNode root){
if(root==null){
return;
}
int v=root.val;
if(root.left!=null){
int w=root.left.val;
G[v].add(w);
G[w].add(v);
dfs(root.left);
}
if(root.right!=null){
int w=root.right.val;
G[v].add(w);
G[w].add(v);
dfs(root.right);
}
}
public List<Integer> distanceK(TreeNode root, TreeNode target, int K) {
List<Integer> res=new ArrayList<>();
if(root==null){
return res;
}
if(K==0){
res.add(target.val);
return res;
}
G=(Vector<Integer>[])new Vector[1005];
for(int i=0;i<1005;i++){
G[i]=new Vector<>();
}
isVisited=new boolean[1005];
//将二叉树转化为获取图
dfs(root);
//从target开始对图进行广度优先遍历
//Pair<Integer,Integer>存的是<顶点，从target到该顶点的距离>
Queue<Pair<Integer,Integer>> queue=new LinkedList<>();
queue.add(new Pair<>(target.val,0));
isVisited[target.val]=true;
while(!queue.isEmpty()){
Pair<Integer,Integer> pair=queue.poll();
int v=pair.getKey();
int distance=pair.getValue();
if(distance==K){
res.add(v);
continue;
}
//遍历与v相邻的顶点
for(Integer w:G[v]){
if(!isVisited[w]){
queue.add(new Pair<>(w,distance+1));
isVisited[w]=true;
}
}
}
return res;
}865 Smallest Subtree with all the Deepest Nodes
/**
* 思路：
* 这个题的模型其实比较左右子树的高度，如果左右子树的高度相等，说明当前节点就是要求的。
* 这个解释是这样的：必须包含所有的最大高度的叶子，左右叶子高度相等，所以必须包含当前节点。
*
* 当左子树高度>右子树高度的时候，要求的节点在左边；反之，在右边。
* 所以，递归思路 + 一个pair。这个pair的思路是，保存了当前节点的深度和当前节点的最深子树节点。
* pair就是< 当前节点的深度，当前节点的最深子树节点>
*/
public TreeNode subtreeWithAllDeepest(TreeNode root) {
if(root==null){
return null;
}
return getNode(root).getValue();
}
private Pair<Integer,TreeNode> getNode(TreeNode root){
if(root==null){
return new Pair<>(-1,null);
}
Pair<Integer,TreeNode> l=getNode(root.left);
Pair<Integer,TreeNode> r=getNode(root.right);
int leftChildDepth=l.getKey();
int rightChildDepth=r.getKey();
int depth=Math.max(leftChildDepth,rightChildDepth)+1;
/**
* 如果左右子树的高度相等，说明当前节点就是要求的。
* 这个解释是这样的：必须包含所有的最大高度的叶子，左右叶子高度相等，所以必须包含当前节点。
*/
TreeNode node= null;
if(leftChildDepth==rightChildDepth){
node = root;
}else if(leftChildDepth>rightChildDepth){
//当左子树高度>右子树高度的时候，要求的节点在左边；反之，在右边。
node = l.getValue();
}else if(leftChildDepth<rightChildDepth){
node = r.getValue();
}
return new Pair<>(depth,node);
}/**
* 思路：直接求出叶子节点，放入指定集合中即可，然后进行比较
*/
public boolean leafSimilar(TreeNode root1, TreeNode root2) {
List<Integer> res1=new ArrayList<>();
List<Integer> res2=new ArrayList<>();
getLeaves(root1,res1);
getLeaves(root2,res2);
if(res1.equals(res2)){
return true;
}
return false;
}
private void getLeaves(TreeNode root,List<Integer> res){
if(root==null){
return;
}
if(root.left==null && root.right==null){
res.add(root.val);
}
getLeaves(root.left,res);
getLeaves(root.right,res);
}- 使用记忆化搜索改进
public List<TreeNode> allPossibleFBT(int N) {
if (N % 2 == 0) {
return new ArrayList<>();
}
//记录<节点数，以该结点数所构造的二叉树的所有可能>
List<TreeNode>[] memo=new ArrayList[N+1];
for(int i=0;i<memo.length;i++){
memo[i]=new ArrayList<>();
}
return allPossibleFBT(N,memo);
}
private List<TreeNode> allPossibleFBT(int N,List<TreeNode>[] memo){
if(memo[N].size()!=0){
return memo[N];
}
if(N==1){
memo[1]=new ArrayList<>(Arrays.asList(new TreeNode(0)));
return memo[1];
}
for(int i=1;i<N;i+=2){
List<TreeNode> leftChild=allPossibleFBT(i);
List<TreeNode> rightChild=allPossibleFBT(N-1-i);
for(TreeNode leftNode:leftChild){
for(TreeNode rightNode:rightChild){
TreeNode root=new TreeNode(0);
root.left=leftNode;
root.right=rightNode;
memo[N].add(root);
}
}
}
return memo[N];
}894 All Possible Full Binary Trees
/**
* 思路：
* 现在考虑有个根节点，它的所有满二叉树组合为allPossibleFBT(N)，
* 左子树可能有的节点数目为1，2，…，i，…，N-1，
* 同时右子树可能有的节点数目为N-1-1，N-2-1，…，N-i-1，…，1。
* 那么我们可以分别得到左右子树的所有满二叉树的组合：
* allPossibleFBT（i）和allPossibleFBT（N-i-1）。
*/
public List<TreeNode> allPossibleFBT1(int N) {
List<TreeNode> res=new ArrayList<>();
if(N==0){
return res;
}
if(N==1){
res.add(new TreeNode(0));
return res;
}
//一个结点只允许两种情况:无节点或者两个节点
for(int i=1;i<=N-1;i+=2){
List<TreeNode> leftChild=allPossibleFBT1(i);
List<TreeNode> rightChild=allPossibleFBT1(N-1-i);
for(TreeNode leftNode:leftChild){
for(TreeNode rightNode:rightChild){
TreeNode root=new TreeNode(0);
root.left=leftNode;
root.right=rightNode;
res.add(root);
}
}
}
return res;
}897 Increasing Order Search Tree
/**
* 思路一
*/
private int[] inorder=new int[200];
private int index;
public TreeNode increasingBST(TreeNode root) {
if(root==null){
return null;
}
inOrder(root);
return buildBST(inorder,0,index-1);
}
private TreeNode buildBST(int[] arr,int start,int end){
if(arr==null || arr.length==0 || start>end){
return null;
}
TreeNode root=new TreeNode(arr[start]);
root.left=null;
root.right=buildBST(arr,start+1,end);
return root;
}
private void inOrder(TreeNode root){
if(root==null){
return;
}
inOrder(root.left);
inorder[index++]=root.val;
inOrder(root.right);
}/**
* 思路二
*/
private TreeNode cur;
public TreeNode increasingBST(TreeNode root) {
if(root==null){
return null;
}
TreeNode dummyNode=new TreeNode(-1);
cur=dummyNode;
inorder(root);
return dummyNode.right;
}
private void inorder(TreeNode root){
if(root==null){
return;
}
inorder(root.left);
cur.right=root;
cur=root;
cur.left=null;
inorder(root.right);
}95 Unique Binary Search Trees II
public List<TreeNode> generateTrees(int n) {
if(n<=0){
return new ArrayList<>();
}
return genenateTree(1,n);
}
//[start,end]的数据产生二叉树
private List<TreeNode> genenateTree(int start,int end){
List<TreeNode> res=new ArrayList<>();
if(start>end){
res.add(null);
return res;
}
for(int i=start;i<=end;i++){
//i值作为根结点，构建该BST树
List<TreeNode> left=genenateTree(start,i-1);
List<TreeNode> right=genenateTree(i+1,end);
for(TreeNode leftNode:left){
for(TreeNode rightNode:right){
TreeNode root=new TreeNode(i);
root.left=leftNode;
root.right=rightNode;
res.add(root);
}
}
}
return res;
}