树的构造

• 105. 从前序与中序遍历序列构造二叉树
• 106. 从中序与后序遍历序列构造二叉树
• 108. 将有序数组转换为二叉搜索树
• 110. 平衡二叉树
• 111. 二叉树的最小深度
• 112. 路径总和
• 113. 路径总和 II
• 114. 二叉树展开为链表
• 116. 填充每个节点的下一个右侧节点指针
• 117. 填充每个节点的下一个右侧节点指针 II
• 235. 二叉搜索树的最近公共祖先
• 236. 二叉树的最近公共祖先
• 230. 二叉搜索树中第K小的元素
• 95. 不同的二叉搜索树 II
• 96. 不同的二叉搜索树
• 101. 对称二叉树

105. 从前序与中序遍历序列构造二叉树

思路：
先序遍历的顺序是根节点，左子树，右子树。中序遍历的顺序是左子树，根节点，右子树。

所以我们只需要根据先序遍历得到根节点，然后在中序遍历中找到根节点的位置，它的左边就是左子树的节点，右边就是右子树的节点。
生成左子树和右子树就可以递归的进行了。

事实上，我们不需要真的把 preorder 和 inorder 切分了，只需要用分别用两个指针指向开头和结束位置即可。注意下边的两个指针指向的数组范围是包括左边界，不包括右边界。
代码：

public TreeNode buildTree(int[] preorder, int[] inorder) {return helper(preorder,0,preorder.length,inorder,0,inorder.length);}
public TreeNode helper(int[] preorder,int p_start,int p_end, int[] inorder,int i_start,int i_end){// preorder 为空，直接返回 nullif (p_start==p_end) return null;int root_val = preorder[p_start];//在中序遍历中找到根节点的位置int root_index=0;for(int i=i_start;i<i_end;i++){if (inorder[i]==root_val){root_index = i;break;}} TreeNode root = new TreeNode(root_val);int left_num = root_index-i_start;//递归的构造左子树root.left = helper(preorder,p_start+1,p_start+1+left_num,inorder,i_start,root_index);//递归的构造右子树root.right = helper(preorder,p_start+1+left_num,p_end,inorder,root_index+1,i_end);return root;
}

上边的代码很好理解，但存在一个问题，在中序遍历中找到根节点的位置每次都得遍历中序遍历的数组去寻找，我们可以用一个HashMap把中序遍历数组的每个元素的值和下标存起来，这样寻找根节点的位置就可以直接得到了。

public TreeNode buildTree(int[] preorder, int[] inorder) {// 根据inorder的值保存其索引HashMap<Integer, Integer> map = new HashMap<>();for (int i = 0; i < inorder.length; i++) {map.put(inorder[i],i);}return helper(preorder,0,preorder.length,inorder,0,inorder.length,map);}
public TreeNode helper(int[] preorder,int p_start,int p_end, int[] inorder,int i_start,int i_end,HashMap<Integer, Integer> map){// preorder 为空，直接返回 nullif (p_start==p_end) return null;int root_val = preorder[p_start];//在中序遍历中找到根节点的位置int root_index = map.get(root_val);TreeNode root = new TreeNode(root_val);int left_num = root_index-i_start;//递归的构造左子树root.left = helper(preorder,p_start+1,p_start+1+left_num,inorder,i_start,root_index,map);//递归的构造右子树root.right = helper(preorder,p_start+1+left_num,p_end,inorder,root_index+1,i_end,map);return root;}

106. 从中序与后序遍历序列构造二叉树

思路同105题
代码：

public TreeNode buildTree(int[] inorder, int[] postorder) {HashMap<Integer,Integer> map = new HashMap<>();for(int i=0;i<inorder.length;i++){map.put(inorder[i],i);}return helper(inorder,0,inorder.length,postorder,0,postorder.length,map);}
public TreeNode helper(int[] inorder,int i_start,int i_end, int[] postorder,int p_start,int p_end,HashMap<Integer,Integer> map){if(i_start==i_end) return null;int root_val = postorder[p_end-1];int i_root_index = map.get(root_val);int i_right_num = i_end-i_root_index-1;TreeNode root = new TreeNode(root_val);root.left = helper(inorder,i_start,i_root_index,postorder,p_start,p_end-i_right_num-1,map);root.right = helper(inorder,i_root_index+1,i_end,postorder,p_end-i_right_num-1,p_end-1,map);return root;
}

108. 将有序数组转换为二叉搜索树

解答：
给定是有序数组，取中间值作为父节点，左边、右边数组分别作为其子树，然后在子树同样选出中间值作为父节点，递归实现，基础情况是：子树数组只有一个则返回此节点，为空返回null
代码：

    public TreeNode sortedArrayToBST(int[] nums) {return helper(nums,0,nums.length-1);}private TreeNode helper(int[] nums,int start,int end) {if (start>end) return null;if (start==end) return new TreeNode(nums[start]);int root_index = start+(end-start)/2; //防止溢出
//        int root_index = (start+end)>>>1;  //如果溢出，进位保存到符号位，>>>右移可实现溢出也能除以2TreeNode root = new TreeNode(nums[root_index]);root.left = helper(nums,start,root_index-1);root.right = helper(nums,root_index+1,end);return root;}

110. 平衡二叉树

方法一： 自顶向下
父节点是否平衡，取决于左右子树高度差，同时左右子树也平衡，本质就是求解树的高度

    public boolean isBalanced(TreeNode root) {if (root==null) return true;return Math.abs(getHeight(root.left)-getHeight(root.right))< 2&& isBalanced(root.left) && isBalanced(root.right);}public int getHeight(TreeNode root){if (root==null) return 0;int left_height = getHeight(root.left);int right_height = getHeight(root.right);return Math.max(left_height,right_height)+1;}

方法二： 自底向上
解法一每次通过左右子树高度差判断父节点是否平衡后，判断子树是否平衡，但又要重新求子树高度，造成冗余，采用自底向上，求子树高度，同时判断子树是否平衡，如果子树不平衡，那么父节点不平衡，否则根据左右子树高度差进行判断，这样就不会重复计算。定义空节点高度为0，单个节点高度为1。

public boolean isBalanced(TreeNode root) {return getHeight(root)!= -1;}
public int getHeight_helper(TreeNode root){if (root==null) return 0;int left_height = getHeight_helper(root.left);if (left_height==-1) return -1;int right_height = getHeight_helper(root.right);if (right_height==-1) return -1;if (Math.abs(left_height-right_height)>1){return -1;}return Math.max(left_height,right_height)+1;
}

参考： leetcode.wang

111. 二叉树的最小深度

思路：
本以为递归算出子树的最小深度，取左右子树最小值即可得到根的最小深度
但一定要注意是到叶子节点的最短路径，例如

如果按照上面的思路，9右节点为null，所以最小深度为1，则3的最小深度为2，显然不符合题意，3-9-8才是最终答案，造成错误的原因就是没有考虑到叶子节点，只有 A.left=null,A.right=null，A才是叶子节点，其深度为1，返回给父节点。如果只有其中一子节点为null，则只考虑另一个子节点的深度即可
代码：

    public int minDepth(TreeNode root) {if (root==null) return 0;//左孩子为空，只考虑右孩子的方向if (root.left == null) return  minDepth(root.right)+1;//右孩子为空，只考虑左孩子的方向if (root.right == null) return  minDepth(root.left)+1;//既有左孩子又有右孩子，那么就选一个较小的int left_height = minDepth(root.left);int right_height = minDepth(root.right);return Math.min(left_height,right_height)+1;}

参考： leetcode.wang

112. 路径总和

方法一： 递归
与111题类似，一定要注意是叶子节点，否则下面这种情况也会判定为true

代码：

    //递归public boolean hasPathSum(TreeNode root, int sum) {if (root==null) return false;int root_val = root.val;if (root.left==null&&root.right==null){if (sum==root_val) return true;return false;}if (root.left==null) return hasPathSum(root.right,sum-root_val);if (root.right==null) return hasPathSum(root.left,sum-root_val);return hasPathSum(root.left,sum-root_val)||hasPathSum(root.right,sum-root_val);}

方法二 ： BFS
使用队列实现BFS，用queue_sum 记录对应节点到根节点所有值之和

    //BFSpublic boolean hasPathSum_BFS(TreeNode root, int sum){if (root==null) return false;Queue<TreeNode> queue = new LinkedList<>();Queue<Integer> queue_sum = new LinkedList<>();queue.offer(root);//sum保存所存储节点到根节点所有值之和queue_sum.offer(root.val);while (!queue.isEmpty()){TreeNode cur = queue.poll();int val = queue_sum.poll();if (cur.left==null&&cur.right==null&&sum==val) return true;if (cur.left!=null){queue.offer(cur.left);queue_sum.offer(cur.left.val+val);}if (cur.right!=null){queue.offer(cur.right);queue_sum.offer(cur.right.val+val);}}return false;}

方法三： BFS
利用栈模拟递归

//DFSpublic boolean hasPathSum_DFS(TreeNode root, int sum){if (root==null) return false;Stack<TreeNode> stack = new Stack<>();Stack<Integer> stack_sum = new Stack<>();stack.push(root);stack_sum.push(root.val);while (!stack.isEmpty()){TreeNode cur = stack.pop();int val = stack_sum.pop();//前序遍历，先处理父节点，然后压右子节点-左子节点if (cur.left==null&cur.right==null&&val==sum) return true;if (cur.right!=null){stack.push(cur.right);stack_sum.push(cur.right.val+val);}if (cur.left!=null){stack.push(cur.left);stack_sum.push(cur.left.val+val);}}return false;}

113. 路径总和 II

给定一个二叉树和一个目标和，找到所有从根节点到叶子节点路径总和等于给定目标和的路径。

说明: 叶子节点是指没有子节点的节点。

解答：
在112题的基础上加上回溯

	List<List<Integer>> res = new LinkedList<>();public List<List<Integer>> pathSum(TreeNode root, int sum) {if (root==null) return res;List<Integer> list = new LinkedList<>();list.add(root.val);//将root作为当前节点，与目标差距sum-root.val，//注意：list为从当前节点到根节点的路径，所以将root存储helper(root,sum-root.val,list);return res;}/*** @param root 当前节点* @param sum 当前节点值累积与目标差距* @param list 从当前节点到根节点的路径*/private void helper(TreeNode root, int sum, List<Integer> list) {if (root.left==null&&root.right==null&&sum==0){//注意要新new一个对象,否则最后res保存的都是同一个listres.add(new LinkedList<>(list));return;}if (root.left!=null){list.add(root.left.val);helper(root.left,sum-root.left.val,list);//回溯恢复listlist.remove(list.size()-1);}if (root.right!=null){list.add(root.right.val);helper(root.right,sum-root.right.val,list);//回溯恢复listlist.remove(list.size()-1);}}

114. 二叉树展开为链表

给定一个二叉树，原地（in-place）将它展开为一个单链表。

思路：
可以发现展开的顺序其实就是二叉树的先序遍历。算法和 94 题 中序遍历的 Morris 算法有些神似，我们需要两步完成这道题。

将左子树插入到右子树的地方
将原来的右子树接到左子树的最右边节点
考虑新的右子树的根节点，一直重复上边的过程，直到新的右子树为 null
代码：

public void flatten(TreeNode root) {TreeNode cur = root;while (cur!=null){TreeNode left = cur.left;//如果左子树为null，直接考虑下一个节点if (left==null) {cur = cur.right;}else {//找到cur的前驱节点TreeNode tail = left;while (tail.right != null) {tail = tail.right;}//cur的前驱节点右指向cur的右子树tail.right = cur.right;//cur原左子树变为cur的右子树cur.right = left;//cur左指针指向nullcur.left = null;//下一次迭代cur = left;}}}

116. 填充每个节点的下一个右侧节点指针

给定一个完美二叉树，其所有叶子节点都在同一层，每个父节点都有两个子节点。二叉树定义如下：

struct Node {int val;Node *left;Node *right;Node *next;
}

填充它的每个 next 指针，让这个指针指向其下一个右侧节点。如果找不到下一个右侧节点，则将 next 指针设置为 NULL。

初始状态下，所有 next 指针都被设置为 NULL。

法一：BFS
BFS使用队列，步骤同层序遍历，只要将队列弹出的节点next指向队首节点，只要注意每一层结尾指向null
代码：

//BFSpublic Node connect(Node root) {if (root==null) return null;Queue<Node> queue = new LinkedList<>();queue.offer(root);while(!queue.isEmpty()){int len = queue.size();for(int i=0;i<len;i++){Node cur = queue.poll();//如果不是最后一个if(i!=len-1){cur.next = queue.peek();}if (cur.left!=null)queue.offer(cur.left);if (cur.right!=null)queue.offer(cur.right);}}return root;}

法二： 迭代（使用已建立的 next 指针）

思路:

一棵树中，存在两种类型的 next 指针。

• 第一种情况是连接同一个父节点的两个子节点。它们可以通过同一个节点直接访问到，因此执行下面操作即可完成连接。

node.left.next = node.right

• 第二种情况在不同父亲的子节点之间建立连接，这种情况不能直接连接。

如果每个节点有指向父节点的指针，可以通过该指针找到 next 节点。如果不存在该指针，则按照下面思路建立连接：
第 N 层节点之间建立 next 指针后，再建立第 N+1 层节点的 next 指针。可以通过 next 指针访问同一层的所有节点，因此可以使用第 N 层的 next 指针，为第 N+1 层节点建立 next 指针。

代码：

    //迭代public Node connect_iterate(Node root){if (root==null) return null;//N层的队首Node head = root;//N层的移动指针,用于N+1层的节点next连接Node cur = root;while (head.left!= null){while(cur!=null){//有共同父节点的next连接cur.left.next = cur.right;if (cur.next!=null){//不同父节点的next连接cur.right.next = cur.next.left;}cur = cur.next;}//下一次迭代head = head.left;cur = head;}return root;}

117. 填充每个节点的下一个右侧节点指针 II

给定一个二叉树
填充它的每个 next 指针，让这个指针指向其下一个右侧节点。如果找不到下一个右侧节点，则将 next 指针设置为 NULL。
初始状态下，所有 next 指针都被设置为 NULL。

思路

• 第一个问题，第N+1层起始点不再是N层head.left，如果上一层获得到过N+1层第一个不为null的节点，N+1层指向此节点即可，那么N层如何判断N+1层第一个不为null的节点呢，如果cur表示N层的移动指针，cur.left!=null则其左子节点即为下一层起始点，否则 cur.right!=null,右子节点为下一层起点，否则cur = cur.next，继续相同判断。根据链表经验，如果头节点状态不固定，可以用一个哑节点dumn指向头节点，一般化头节点，这样dumn.next就固定指向起始点
• 这样下一层cur即为dumn.next
• 同时每一个要连接的next的右节点即为下一个连接的左节点，如果用tail表示连接起点，即 tail=tail.next
  

参考：leetcode.wang
代码：

    //迭代public Node connect(Node root) {Node cur = root;while (cur!=null){Node dumn = new Node();Node tail = dumn;while (cur!=null){if (cur.left!=null){tail.next = cur.left;tail = tail.next;}if (cur.right!=null){tail.next = cur.right;tail = tail.next;}cur = cur.next;}//更新 cur 到下一层cur = dumn.next;}return root;}

235. 二叉搜索树的最近公共祖先

给定一个二叉搜索树, 找到该树中两个指定节点的最近公共祖先。

百度百科中最近公共祖先的定义为：“对于有根树 T 的两个结点 p、q，最近公共祖先表示为一个结点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。”

例如，给定如下二叉搜索树: root = [6,2,8,0,4,7,9,null,null,3,5]

思路：
利用搜索二叉树的性值，同时避开p/q本身是公共祖先的情况

• 如果root的val同时大于p、q的值，向root的左子树递归
• 如果root的val同时小于p、q的值，向root的右子树递归
• 否则说明p、q在root异侧或者p或q的值同root值，返回root
  代码：

public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {if (root==null) return null;if (root.val>p.val&&root.val>q.val){return lowestCommonAncestor(root.left,p,q);}else if (root.val < p.val&&root.val < q.val){return lowestCommonAncestor(root.right,p,q);}else {return root;}}

236. 二叉树的最近公共祖先

给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。
思路一： 递归

代码：

    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {if (root==null||root==p||root==q) return root;TreeNode left =  lowestCommonAncestor(root.left,p,q);TreeNode right =  lowestCommonAncestor(root.right,p,q);//在左子树中没有找到，则返回右子树中if (left == null) return right;//在右子树中没有找到，则返回左子树中if (right==null) return left;//如果left!=null && right!=null,root即为最近公共祖先return root;}

参考：力扣

注意：本方法对于情况3.2即p节点是q的祖先这类情况，对于本题输入样本的p、q都一定是树的子节点，但如果输入不在树中，比如p在树中，q不在，返回p。当然对于本体来说没问题。

下面方法二，采用不同思路，通过寻找p、q的路径，如果q、p有公共祖先，找出路径分叉点即可
思路二：路径-回溯法
利用回溯法寻找p、q的路径，然后判断分叉点

//通过路径判断public TreeNode lowestCommonAncestor_path(TreeNode root, TreeNode p, TreeNode q) {if (root==null) return null;LinkedList<TreeNode> p_path = new LinkedList<>();helper(root,p,new ArrayList<>(),p_path);LinkedList<TreeNode> q_path = new LinkedList<>();helper(root,q,new ArrayList<>(),q_path);for (TreeNode node_q : q_path) {for (TreeNode node_p : p_path) {if (node_p==node_q) return node_p;}}return null;}public void helper(TreeNode root, TreeNode p, ArrayList<TreeNode> list,LinkedList<TreeNode> res){if(root==p){list.add(root);for (TreeNode node : list) {res.add(0,node);}list.remove(list.size()-1);return;}if (root.left!=null){list.add(root);helper(root.left,p,list,res);list.remove(list.size()-1);}if (root.right!=null){list.add(root);helper(root.right,p,list,res);list.remove(list.size()-1);}}

思路三：路径-hashMap储存父节点法
思路与法二相同，只是保存路径的方法不同

参考：leetcode.wang

230. 二叉搜索树中第K小的元素

给定一个二叉搜索树，编写一个函数 kthSmallest 来查找其中第 k 个最小的元素。

说明：
你可以假设 k 总是有效的，1 ≤ k ≤ 二叉搜索树元素个数。

    int res = 0;public int kthSmallest(TreeNode root, int k) {int cnt = 0;helper(root,k,cnt);return res;}/*** @param root 当前节点* @param k 寻找第k小，二叉搜索树中序遍历第k个即第k小* @param cnt 当前节点是第几个*/private int helper(TreeNode root, int k, int cnt) {//中序遍历if (root.left!=null) {cnt = helper(root.left,k,cnt);}cnt = cnt+1;if (cnt==k) {res = root.val;return cnt;}if (root.right!=null) {cnt = helper(root.right,k,cnt);}return cnt;}

95. 不同的二叉搜索树 II

给定一个整数 n，生成所有由 1 … n 为节点所组成的 二叉搜索树 。

思路：
由于暴力回溯没有利用搜索树的性值一定会产生n!种结果，考虑到搜索树的性值，左子树的节点值小于父节点，右子树的节点值大于父节点，对于排列的数组[1,2,3…n]，选择一个作为父节点，其左侧子数组即为左子树，右侧数组即为右子树，左右子树分别选出父节点作为当前根的子节点，由于父节点选择是多样的，所以用List存储不同情况的父节点。显然子树可以进行同样的操作，即可递归操作，当子树为空则返回内涵null节点的list，即为递归终止条件。

代码：

    public List<TreeNode> generateTrees(int n) {if (n==0) return new ArrayList<>();return helper(1,n);}public List<TreeNode> helper(int start,int end){//用List存储所有可能情况的父节点List<TreeNode> list = new ArrayList<>();if (start>end) {list.add(null);return list;}for (int i = start; i <= end; i++) {//所有可能的左子树List<TreeNode> left = helper(start,i-1);//所有可能的右子树List<TreeNode> right = helper(i+1,end);for (TreeNode r : right) {for (TreeNode l : left) {TreeNode cur = new TreeNode(i);cur.left = l;cur.right = r;list.add(cur);}}}return list;}

96. 不同的二叉搜索树

给定一个整数 n，求以 1 … n 为节点组成的二叉搜索树有多少种？
思路：
和95题类似，但只要求出数量即可，发现不管子树各节点数值是多少，只要节点数相同，子树返回的结果就相同，父节点返回的结果即为左右节点的乘积
代码：

public int numTrees(int n) {if (n==0) return 0;// 缓存已求过的结果int[] arr =new int[n+1];return helper(n,arr);}
//只关心左右子树节点的数量，然后左*右即可
public int helper(int n,int[] arr){if (n==0||n==1) return 1;int res = 0;for (int i = 1; i <= n; i++) {//如果结果已得到过，直接过去int l = arr[i-1]==0?helper(i-1,arr):arr[i-1];int r = arr[n-i]==0?helper(n-i,arr):arr[n-i];//左子树右子树两两组合res += l*r;}//保存结果arr[n] = res;return res;
}

数学公式法-卡特兰数参见：力扣

101. 对称二叉树

给定一个二叉树，检查它是否是镜像对称的。

思路1：递归
判断树是否镜像对称，可以用两个指针A、B分别位于镜面两侧，判断其值是否相等，若相等再判断A.leftB.right?与A.rightB.left?，这样就能递归判断下去了，终止递归条件就是A、B都为Null或者只有一个为Null。

public boolean isSymmetric(TreeNode root){if (root==null) return true;return helper(root.left,root.right);}private boolean helper(TreeNode left, TreeNode right) {if (left==null&&right==null) return true;if (left==null||right==null) return false;return left.val!=right.val&&helper(left.left,right.right)&&helper(left.right,right.left);}

思路2：迭代
思路与递归相似，将需要比较的两个节点一次存入队列，之后也是连续取出进行比较
代码：

Queue<TreeNode> queue = new LinkedList<>();if (root==null) return true;queue.add(root.left);queue.add(root.right);while (!queue.isEmpty()){TreeNode left = queue.poll();TreeNode right = queue.poll();//只有返回false才能直接return，不然只是continueif (left==null&&right==null) continue;if (left==null||right==null) return false;if (left.val!=right.val) return false;queue.add(left.left);queue.add(right.right);queue.add(left.right);queue.add(right.left);}return true;