- BST（二叉搜索树）的中序遍历结果，就得到了树的小->大的遍历
- （95）给一个数字n，提供所有可行的BST
Given n, how many structurally unique BST's (binary search trees) that store values 1...n?
For example,
Given n = 3, there are a total of 5 unique BST's.
1 3 3 2 1
\ / / / \
3 2 1 1 3 2
/ / \
2 1 2 3
- 用递归思想
- 每次选取一个节点作为跟，然后递归求解左右子树的所有结果，最后根据左右子树的返回的所有子树，依次选取然后接上（每个左边的子树跟所有右边的子树匹配，而每个右边的子树也要跟所有的左边子树匹配，总共有左右子树数量的乘积种情况），构造好之后作为当前树的结果返回
public ArrayList<TreeNode> generateTrees(int n) {
return helper(1,n);
}
private ArrayList<TreeNode> helper(int left, int right)
{
ArrayList<TreeNode> res = new ArrayList<TreeNode>();
if(left>right)
{
res.add(null);
return res;
}
for(int i=left;i<=right;i++)
{
ArrayList<TreeNode> leftList = helper(left,i-1);
ArrayList<TreeNode> rightList = helper(i+1,right);
for(int j=0;j<leftList.size();j++)
{
for(int k=0;k<rightList.size();k++)
{
TreeNode root = new TreeNode(i);
root.left = leftList.get(j);
root.right = rightList.get(k);
res.add(root);
}
}
}
return res;
}
2.2 (96)给定一个数字n，有多少个唯一二叉搜索树
Given n, how many structurally unique BST's (binary search trees) that store values 1...n?
For example,
Given n = 3, there are a total of 5 unique BST's.
1 3 3 2 1
\ / / / \
3 2 1 1 3 2
/ / \
2 1 2 3
思路：
用一个数组保存 1 至 n-1 对应的不同二叉树的个数 X1、X2、X3、... Xn-1，
则 n 对应的不同二叉树个数Xn = Xn-1 + X1Xn-2 + X2Xn-3 + X3Xn-4 + ... + Xn-2X1 + Xn-1
// 动态规划
public int numTrees(int n) {
if (n == 0 || n == 1) {
return 1;
}
int sum = 0;
for(int i = 1; i <= n; ++i) {
sum += numTrees(i - 1) * numTrees(n - i);
}
return sum;
}
- 之字形 遍历一棵树
- 用两个栈来倒数据
- 有一个方向变量
public class Solution {
public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
List<List<Integer>> result = new ArrayList<List<Integer>>();
if (root == null) {
return result;
}
Stack<TreeNode> currLevel = new Stack<TreeNode>();
Stack<TreeNode> nextLevel = new Stack<TreeNode>();
Stack<TreeNode> tmp;
currLevel.push(root);
boolean normalOrder = true;
while (!currLevel.isEmpty()) {
ArrayList<Integer> currLevelResult = new ArrayList<Integer>();
while (!currLevel.isEmpty()) {
TreeNode node = currLevel.pop();
currLevelResult.add(node.val);
if (normalOrder) {
if (node.left != null) {
nextLevel.push(node.left);
}
if (node.right != null) {
nextLevel.push(node.right);
}
} else {
if (node.right != null) {
nextLevel.push(node.right);
}
if (node.left != null) {
nextLevel.push(node.left);
}
}
}
result.add(currLevelResult);
tmp = currLevel;
currLevel = nextLevel;
nextLevel = tmp;
normalOrder = !normalOrder;
}
return result;
}
}
- 如何判断一个排好序的数列里，有哪两个数字颠倒了？
// 用于存储当前找到的发生交换的数
int first = -1, second;
// 从前往后依次寻找逆序并相邻的数字对
for (int i = 0; i < n; i++) {
// 存在逆序
if (i > 0 && val[i] < val[i - 1]) {
// 如果当前一对都没有找到
if (first == -1) {
// 不放先假设只有一对
first = i - 1; second = i;
}
else {
// 存在两对，只需要修改second
second = i;
}
}
}
- 和上题类似的场景，但是是发生在BST中的两个节点被调换。在中序遍历过程中，在处理current节点时可以做类似于上述 找first 和 找second的事情
public class Solution {
TreeNode firstNode;
TreeNode secondNode;
TreeNode lastNode;
public void recoverTree(TreeNode root) {
inorderTraversal(root);
int tmp = firstNode.val;
firstNode.val = secondNode.val;
secondNode.val = tmp;
}
private void inorderTraversal(TreeNode root) {
if(root == null)
return;
inorderTraversal(root.left);
if(lastNode != null && firstNode == null && lastNode.val >= root.val)
firstNode = lastNode;
if(lastNode != null && firstNode != null && lastNode.val >= root.val)
secondNode = root;
lastNode = root; // lastNode，用于帮助发现firstNode
inorderTraversal(root.right);
}
}
- 利用先序+中序遍历结果，构建二叉树
- 先序遍历的第一位： tree's root
- 中序遍历某节点的左侧：该节点的左子树
- 中序遍历某节点的右侧：该节点的右子树
public class Solution {
private int findPosition(int[] arr, int start, int end, int key) {
int i;
for (i = start; i <= end; i++) {
if (arr[i] == key) {
return i;
}
}
return -1;
}
private TreeNode myBuildTree(int[] inorder, int instart, int inend,
int[] preorder, int prestart, int preend) {
if (instart > inend) {
return null;
}
TreeNode root = new TreeNode(preorder[prestart]);
int position = findPosition(inorder, instart, inend, preorder[prestart]);
root.left = myBuildTree(inorder, instart, position - 1,
preorder, prestart + 1, prestart + position - instart);
root.right = myBuildTree(inorder, position + 1, inend,
preorder, position - inend + preend + 1, preend);
return root;
}
public TreeNode buildTree(int[] preorder, int[] inorder) {
if (inorder.length != preorder.length) {
return null;
}
return myBuildTree(inorder, 0, inorder.length - 1, preorder, 0, preorder.length - 1);
}
}
- 上题拓展： 利用后续遍历+中序遍历，输出BST
- 后续遍历的最后一位，代表了tree's root
- 层次遍历的非递归方式：利用队列queue.
加大难度， 返回其节点值从底向上的层次序遍历（按从叶节点所在层到根节点所在的层遍历，然后逐层从左往右遍历）
public List<List<Integer>> levelOrderBottom(TreeNode root) {
List<List<Integer>> result = new ArrayList<>();
if (root == null) {
return result;
}
Queue<TreeNode> queue = new LinkedList<TreeNode>();
queue.offer(root);
while (!queue.isEmpty()) {
int size = queue.size();
List<Integer> level = new ArrayList<>();
for (int i = 0; i < size; i++) {
TreeNode head = queue.poll();
level.add(head.val);
if (head.left != null) {
queue.offer(head.left);
}
if (head.right != null) {
queue.offer(head.right);
}
}
result.add(level);
}
Collections.reverse(result);
return result;
}
- 给定一棵完全二叉树，计算它的节点数
思路：分别找出以当前节点为根节点的左子树和右子树的高度并对比，如果相等，则说明是满二叉树，直接返回节点个数，如果不相等，则节点个数为左子树的节点个数加上右子树的节点个数再加1(根节点)
class Solution {
public int countNodes(TreeNode root) {
if(root == null)
return 0;
TreeNode left = root;
TreeNode right = root;
int left_high =0, right_high=0;
// 通过寻找最左节点，查看左子树的深度
while(left!=null){
left_high ++;
left = left.left;
}
// 通过寻找最右节点，查看右子树的深度
while(right!=null){
right_high ++;
right = right.right;
}
if(left_high == right_high){
return (int)(Math.pow(2, left_high))-1;
}else{
return 1 + countNodes(root.left) + countNodes(root.right) ;
}
}
}
- 【House Robber3】 后续遍历(先然后子节点do-job,然后父节点综合考虑子节点的数据 进一步计算)
所有邻居都形成一颗二叉树，树上偷相邻节点的情况会报警。求抢劫钱数最大值
这里用map来记下当前结点的和，避免一些重复记算
class Solution {
Map<TreeNode, Integer> map = new HashMap<TreeNode, Integer>();
public int rob(TreeNode root) {
if(root == null)
return 0;
if(map.containsKey(root)){
return map.get(root);
}
int take = root.val;
if(root.left != null){
take += rob(root.left.left) + rob(root.left.right);
}
if(root.right != null){
take += rob(root.right.left) + rob(root.right.right);
}
int notTake = rob(root.left) + rob(root.right) ;
int max = Math.max(take, notTake);
map.put(root, max);
return max;
}
}
- 如何判断一个树是否是完全二叉树
分情况判断：
① 一个节点有右子树，但是没有左子树那么他一定不是完全二叉树
② 一个节点的左右子树不满，那说明从他之后的节点都应该是叶节点，才满足完全二叉树。
那么就利用BFS广度优先遍历，遇到情况1直接返回false，遇到情况2然后进行标记，看后边节点是否有子节点。 有的话直接返回false
public static boolean isCbtForSerch(TreeNodes tree){
Queue<TreeNodes> que =new LinkedList<>();
que.add(tree);
boolean isCaseTwo =false;
while(!que.isEmpty()){
tree =que.poll();
//undo 判断他是那种情况
// case one :only have right don t have left
if((tree.right!=null&&tree.left==null) ||
(isCaseTwo&&(tree.left!=null||tree.right!=null))){
return false;
}
if(tree.left!=null){
que.add(tree.left);
}
if(tree.right!=null){
que.add(tree.right);
}else{
isCaseTwo=true;
}
}
return true;
}
- 计算完全二叉树的节点个数
如果左子树不是满二叉树 右子树一定是满二叉树 。满二叉树计算是数学公式 2^高度-1计算出来的。 就可以将一颗二叉树分为 满二叉树+ 递归判断另一边完全二叉树的节点个数。
即可分为以下几种情况 ：
- 左子树是满二叉树 ，结果等于 2^高度 -1 +递归右子树
- 右子树是满二叉树 结果等于 2^(高度 -1) +递归左子树
如果判断左右两边，哪边是满的呢？
以头结点右孩子为头结点同样进行深度计算。如果depth(root) - depth(root->right) = 1，说明右边不满 左边满的。如果不是相差1 那么就是左边不满，右边满 。
class Solution {
public int countNodes(TreeNode root) {
if(root == null){
return 0;
}
int left = countLevel(root.left);
int right = countLevel(root.right);
if(left == right){
return countNodes(root.right) + (1<<left);
}else{
return countNodes(root.left) + (1<<right);
}
}
private int countLevel(TreeNode root){
int level = 0;
while(root != null){
level++;
root = root.left;
}
return level;
}
}
作者：xiao-ping-zi-5
链接：https://leetcode-cn.com/problems/count-complete-tree-nodes/solution/chang-gui-jie-fa-he-ji-bai-100de-javajie-fa-by-xia/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
- 先序遍历的非递归写法
/**
* 非递归先序遍历二叉树
* */
public List<Integer> preorderTraversal(TreeNode root) {
List<Integer> resultList=new ArrayList<>();
Stack<TreeNode> stack=new Stack<>();
if(root==null) //如果为空树则返回
return resultList;
stack.push(root);
while(!stack.isEmpty()){
TreeNode tempNode=stack.pop();
if(tempNode!=null){
resultList.add(tempNode.val);//访问根节点
stack.push(tempNode.right); //入栈右孩子
stack.push(tempNode.left);//入栈左孩子
}
}
return resultList;
}
- 中序遍历的非递归写法
List<Integer> resultList = new ArrayList<Integer>();
Stack<TreeNode> stack = new Stack<>();
// root为空且stack为空，遍历结束
while (root != null || !stack.isEmpty()) {
// 先根后左入栈
while (root != null) {
stack.push(root);
root = root.left;
}
root = stack.pop();
resultList.add(root.val);
root = root.right;
}
return resultList;
- 后序遍历的非递归写法
// 把前序遍历的结果reverse一下
Stack<TreeNode> stack = new Stack<>();
stack.push(root);
List<Integer> ret = new ArrayList<>();
while (!stack.isEmpty()) {
TreeNode node = stack.pop();
if (node != null) {
ret.add(node.val);
stack.push(node.left);
stack.push(node.right);
}
}
Collections.reverse(ret);
return ret;
网友评论