牛客top100 -自刷打卡day2+3 - 二叉树

• • 二叉树
  • • BM23二叉树的前序遍历
    • BM24二叉树的中序遍历
    • BM25二叉树的后序遍历
    • BM26求二叉树的层序遍历
    • BM27按之字形顺序打印二叉树
    • BM28二叉树的最大深度
    • BM29二叉树中和为某一值的路径(一)
    • BM30二叉搜索树与双向链表
    • BM31对称的二叉树
    • BM32合并二叉树
    • BM33二叉树的镜像
    • BM34判断是不是二叉搜索树
    • BM35判断是不是完全二叉树
    • BM36判断是不是平衡二叉树
    • BM37二叉搜索树的最近公共祖先
    • BM38在二叉树中找到两个节点的最近公共祖先
    • BM39序列化二叉树
    • BM40重建二叉树
    • BM41输出二叉树的右视图

二叉树

BM23二叉树的前序遍历

二叉树的前序遍历_牛客题霸_牛客网 (nowcoder.com)

• 递归, 秒

import java.util.*;/** public class TreeNode {*   int val = 0;*   TreeNode left = null;*   TreeNode right = null;*   public TreeNode(int val) {*     this.val = val;*   }* }*/public class Solution {/*** 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可** * @param root TreeNode类 * @return int整型一维数组*/List list = new ArrayList<>();public void preorder(TreeNode root){if(root == null) {return ;}list.add(root.val);preorder(root.left);preorder(root.right);}public int[] preorderTraversal (TreeNode root) {// write code hereif(root == null) return new int[0];preorder(root);int[] res = new int[list.size()];for(int i = 0; i < list.size(); i++) {res[i] = list.get(i);}return res;}
}

• 非递归

BM24二叉树的中序遍历

二叉树的中序遍历_牛客题霸_牛客网 (nowcoder.com)

• 递归

import java.util.*;/** public class TreeNode {*   int val = 0;*   TreeNode left = null;*   TreeNode right = null;*   public TreeNode(int val) {*     this.val = val;*   }* }*/public class Solution {/*** 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可** * @param root TreeNode类 * @return int整型一维数组*/ArrayList list = new ArrayList<>();public void inorderHelp(TreeNode root){if(root == null) return ;inorderHelp(root.left);list.add(root.val);inorderHelp(root.right);}public int[] inorderTraversal (TreeNode root) {// write code hereif(root == null) return new int[0];inorderHelp(root);int[] res = new int[list.size()];for(int i = 0; i < res.length; i++) {res[i] = list.get(i);}return res;}
}

• 非递归

import java.util.*;/** public class TreeNode {*   int val = 0;*   TreeNode left = null;*   TreeNode right = null;*   public TreeNode(int val) {*     this.val = val;*   }* }*/public class Solution {/*** 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可** * @param root TreeNode类 * @return int整型一维数组*/public int[] inorderTraversal (TreeNode root) {// write code hereif(root == null) return new int[0];List list = new ArrayList<>();Stack stack = new Stack<>();TreeNode cur = root;while(cur != null || !stack.empty()){while(cur != null) {stack.push(cur);cur = cur.left;}TreeNode top = stack.pop();list.add(top.val);cur = top.right;}int []res = new int[list.size()];for(int i = 0; i < res.length; i++) {res[i] = list.get(i);}return res
;}
}

BM25二叉树的后序遍历

二叉树的后序遍历_牛客题霸_牛客网 (nowcoder.com)

• 非递归

import java.util.*;/** public class TreeNode {*   int val = 0;*   TreeNode left = null;*   TreeNode right = null;*   public TreeNode(int val) {*     this.val = val;*   }* }*/public class Solution {/*** 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可** * @param root TreeNode类 * @return int整型一维数组*/public int[] postorderTraversal (TreeNode root) {// write code hereif(root == null) return new int[0];Stack stack = new Stack<>();List list = new ArrayList<>();TreeNode cur = root;TreeNode pre = null;while(cur != null || !stack.empty()) {while(cur != null) {stack.push(cur);cur = cur.left;}TreeNode top = stack.peek();if(top.right == null || top.right == pre){stack.pop();list.add(top.val);pre = top;}else{cur = top.right;}}int []res = new int[list.size()];for(int i = 0; i < res.length; i++) {res[i] = list.get(i);}return res;}
}

BM26求二叉树的层序遍历

import java.util.*;/** public class TreeNode {*   int val = 0;*   TreeNode left = null;*   TreeNode right = null;* }*/public class Solution {/**** @param root TreeNode类* @return int整型ArrayList>*/public ArrayList> levelOrder (TreeNode root) {ArrayList> res = new ArrayList<>();if(root == null) return res;// write code hereQueue q = new LinkedList<>();TreeNode cur = root;q.offer(cur);while (!q.isEmpty()) {ArrayList list = new ArrayList<>();int size = q.size();for(int i = 0; i < size; i++){TreeNode top = q.poll();list.add(top.val);if(top.left != null) q.offer(top.left);if(top.right != null) q.offer(top.right);}res.add(list);}return res;}
}

BM27按之字形顺序打印二叉树

按之字形顺序打印二叉树_牛客题霸_牛客网 (nowcoder.com)

• Collections.reverse, 逆序输出

import java.util.ArrayList;
import java.util.*;
/*
public class TreeNode {int val = 0;TreeNode left = null;TreeNode right = null;public TreeNode(int val) {this.val = val;}}
*/
public class Solution {public ArrayList > Print(TreeNode pRoot) {ArrayList> res = new ArrayList<>();if (pRoot == null) return res;Queue queue = new LinkedList<>();TreeNode cur = pRoot;queue.offer(cur);boolean iflag = true;while (!queue.isEmpty()) {ArrayList list = new ArrayList<>();int size = queue.size();for (int i = 0; i < size; i++) {TreeNode top = queue.poll();list.add(top.val);if (top.left != null) queue.offer(top.left);if (top.right != null) queue.offer(top.right);}if (iflag) res.add(list);else {Collections.reverse(list);res.add(list);}iflag = !iflag;}return res;}}

BM28二叉树的最大深度

二叉树的最大深度

• 秒

import java.util.*;/** public class TreeNode {*   int val = 0;*   TreeNode left = null;*   TreeNode right = null;* }*/public class Solution {/*** * @param root TreeNode类 * @return int整型*/public int maxDepth (TreeNode root) {// write code hereif(root == null) return 0;if(root.left == null && root.right == null) {return 1;}int left = maxDepth(root.left);int right = maxDepth(root.right);return left > right ? left + 1 : right + 1;}
}

BM29二叉树中和为某一值的路径(一)

二叉树中和为某一值的路径(一)

• 注意要结束条件, 当节点的左节点和右节点都为空且此时的sum为0的时候, 这时候就表明找到了

import java.util.*;/** public class TreeNode {*   int val = 0;*   TreeNode left = null;*   TreeNode right = null;* }*/public class Solution {/*** * @param root TreeNode类 * @param sum int整型 * @return bool布尔型*/public boolean hasPathSum (TreeNode root, int sum) {// write code hereif(root == null) return false;return dfs(root, sum);}public boolean dfs(TreeNode root, int sum) {if(root == null) {return false;}if(root.left == null && root.right == null && sum - root.val == 0) return true;return dfs(root.left, sum - root.val) || dfs(root.right, sum - root.val);}
}

BM30二叉搜索树与双向链表

二叉搜索树与双向链表

/**
public class TreeNode {int val = 0;TreeNode left = null;TreeNode right = null;public TreeNode(int val) {this.val = val;}}
*/
public class Solution {public TreeNode head = null;public TreeNode pre = null;public TreeNode Convert(TreeNode pRootOfTree) {if(pRootOfTree == null) {return null;}Convert(pRootOfTree.left);if(pre == null){head = pRootOfTree;pre = pRootOfTree;}else{pre.right = pRootOfTree;pRootOfTree.left = pre;pre = pRootOfTree;}Convert(pRootOfTree.right);return head;}
}

BM31对称的二叉树

对称的二叉树

/*
public class TreeNode {int val = 0;TreeNode left = null;TreeNode right = null;public TreeNode(int val) {this.val = val;}}
*/
public class Solution {boolean isSame(TreeNode root1, TreeNode root2) {if(root1 == null && root2 == null) return true;if(root1 == null || root2 == null) return false;if (root1.val != root2.val) {return false;}return isSame(root1.left, root2.right) && isSame(root1.right, root2.left);}boolean isSymmetrical(TreeNode pRoot) {if (pRoot == null) return true;return isSame(pRoot, pRoot);}
}

思路简单33.53%

视频题解

BM32合并二叉树

合并二叉树

import java.util.*;/** public class TreeNode {*   int val = 0;*   TreeNode left = null;*   TreeNode right = null;* }*/public class Solution {/*** * @param t1 TreeNode类 * @param t2 TreeNode类 * @return TreeNode类*/public TreeNode mergeTrees (TreeNode t1, TreeNode t2) {// write code hereif(t1 == null) return t2;if(t2 == null) return t1;TreeNode head = new TreeNode(-1);if(t1 != null && t2 != null) {head.val = t1.val + t2.val;}head.left = mergeTrees(t1.left, t2.left);head.right = mergeTrees(t1.right, t2.right);return head;}
}

思路简单72.89%

视频题解

BM33二叉树的镜像

二叉树的镜像

import java.util.*;/** public class TreeNode {*   int val = 0;*   TreeNode left = null;*   TreeNode right = null;*   public TreeNode(int val) {*     this.val = val;*   }* }*/public class Solution {/*** 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可*** @param pRoot TreeNode类* @return TreeNode类*/public TreeNode Mirror (TreeNode pRoot) {// write code hereif (pRoot == null) return null;TreeNode left = Mirror(pRoot.left);TreeNode right = Mirror(pRoot.right);//交换pRoot.left = right;pRoot.right = left;return pRoot;}
}

思路简单67.58%

BM34判断是不是二叉搜索树

判断是不是二叉搜索树

import java.util.*;/** public class TreeNode {*   int val = 0;*   TreeNode left = null;*   TreeNode right = null;*   public TreeNode(int val) {*     this.val = val;*   }* }*/public class Solution {/*** 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可** * @param root TreeNode类 * @return bool布尔型*/private boolean BST(TreeNode root, int left, int right){if(root == null) return true;// write code hereif(root.val<=left||root.val>=right){return false;}return BST(root.left, left, root.val) && BST(root.right, root.val, right);}public boolean isValidBST (TreeNode root) {return BST(root, Integer.MIN_VALUE,  Integer.MAX_VALUE);}
}

思路中等33.42%

BM35判断是不是完全二叉树

判断是不是完全二叉树

思路中等39.10%

import java.util.*;/** public class TreeNode {*   int val = 0;*   TreeNode left = null;*   TreeNode right = null;*   public TreeNode(int val) {*     this.val = val;*   }* }*/public class Solution {/*** 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可*** @param root TreeNode类* @return bool布尔型*/public boolean isCompleteTree (TreeNode root) {// write code hereif (root == null) return false;Queue q = new LinkedList<>();q.offer(root);while (!q.isEmpty()) {TreeNode c = q.poll();if (c != null) {q.offer(c.left);q.offer(c.right);} else {break;}}//遍历第二次while (!q.isEmpty()) {TreeNode node = q.peek();if (node == null) {q.poll();} else {return false;}}return true;}
}

BM36判断是不是平衡二叉树

判断是不是平衡二叉树

public class Solution {public int depth(TreeNode root){if(root == null) {return 0;}int lh = depth(root.left) + 1;int rh = depth(root.right) + 1;return lh > rh ? lh : rh;}public boolean IsBalanced_SolutionHelp(TreeNode root){int left = depth(root.left);int right = depth(root.right);if(Math.abs(left - right) <= 1){return IsBalanced_Solution(root.left) && IsBalanced_Solution(root.right);}return false;}public boolean IsBalanced_Solution(TreeNode root) {if(root == null) {return true;}return IsBalanced_SolutionHelp(root);}
}

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

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

思路简单49.56%

import java.util.*;/** public class TreeNode {*   int val = 0;*   TreeNode left = null;*   TreeNode right = null;*   public TreeNode(int val) {*     this.val = val;*   }* }*/public class Solution {/*** 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可** * @param root TreeNode类 * @param p int整型 * @param q int整型 * @return int整型*/public int lowestCommonAncestor (TreeNode root, int p, int q) {// write code hereif(root == null) return -1;if((p >= root.val && q <= root.val) || (p <= root.val && q >= root.val)){return root.val;}else if(p <= root.val && q <= root.val){return lowestCommonAncestor(root.left, p, q);}else{return lowestCommonAncestor(root.right, p, q);}}
}

import java.util.*;/** public class TreeNode {*   int val = 0;*   TreeNode left = null;*   TreeNode right = null;*   public TreeNode(int val) {*     this.val = val;*   }* }*/public class Solution {/*** 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可** * @param root TreeNode类 * @param p int整型 * @param q int整型 * @return int整型*/public int lowestCommonAncestor (TreeNode root, int p, int q) {// write code hereif(root == null) return -1;if(root.val == p){return p;}if(root.val == q){return q;}int left = lowestCommonAncestor(root.left, p, q);int right = lowestCommonAncestor(root.right, p, q);if(left != -1 && right != -1){return root.val;}else if (left != -1){return left;}else if(right != -1){return right;}return -1;}
}

BM38在二叉树中找到两个节点的最近公共祖先

在二叉树中找到两个节点的最近公共祖先

思路中等45.26%

import java.util.*;/** public class TreeNode {*   int val = 0;*   TreeNode left = null;*   TreeNode right = null;* }*/public class Solution {/*** * @param root TreeNode类 * @param o1 int整型 * @param o2 int整型 * @return int整型*/public int lowestCommonAncestor (TreeNode root, int o1, int o2) {// write code hereif(root == null) return -1;if(root.val == o1){return o1;}if(root.val == o2){return o2;}int left = lowestCommonAncestor(root.left, o1, o2);int right = lowestCommonAncestor(root.right, o1, o2);if(left != -1 && right != -1){return root.val;}else if (left != -1){return left;}else if(right != -1){return right;}return -1;}}                                                                                         

BM39序列化二叉树

序列化二叉树

思路较难25.04%

• …过了

BM40重建二叉树

重建二叉树

思路中等27.70%

import java.util.*;
/*** Definition for binary tree* public class TreeNode {*     int val;*     TreeNode left;*     TreeNode right;*     TreeNode(int x) { val = x; }* }*/
public class Solution {public int preIndex = 0;public TreeNode reConstructBinaryTree(int [] pre,int [] vin) {return buildTreeChild(pre, vin, 0, vin.length - 1); }public TreeNode buildTreeChild(int[] pre, int[] vin, int begin, int end){if(begin > end) return null;TreeNode root = new TreeNode(pre[preIndex]);//找到中序遍历中节点位置int rootIndex = findInoederIndex(vin, begin, end, root.val);preIndex++;root.left = buildTreeChild(pre, vin, begin, rootIndex - 1);root.right = buildTreeChild(pre, vin, rootIndex + 1, end);return root;}public int findInoederIndex(int[] inorder, int begin, int end, int val){for(int i = begin; i <= end; i++) {if(inorder[i] == val){return i;}}return -1;}
}

BM41输出二叉树的右视图

输出二叉树的右视图

思路中等56.99%

import java.util.*;public class Solution {/*** 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可* 求二叉树的右视图* @param xianxu int整型一维数组 先序遍历* @param zhongxu int整型一维数组 中序遍历* @return int整型一维数组*/private HashMap ans = new HashMap<>();private HashMap map = new HashMap<>();public int[] solve (int[] xianxu, int[] zhongxu) {// write code herefor (int i = 0; i < zhongxu.length; i++) {map.put(zhongxu[i], i);}build(xianxu, zhongxu, 0, xianxu.length - 1, 0);int[] tmp = new int[ans.size()];for (int i = 0; i < ans.size(); i++) {tmp[i] = ans.get(i);}return tmp;}//pIndex表示先序遍历的顺序ipublic int pIndex = 0;//index表示层级public void build(int[] xianxu, int[] zhongxu, int left, int right, int index) {if (left > right) {return ;}//找到在中序遍历中pIndex对应的值的下标int pindex = map.get(xianxu[pIndex++]);//左子树build(xianxu, zhongxu, left, pindex - 1, index + 1);//右子树build(xianxu, zhongxu, pindex + 1, right, index + 1);ans.put(index, zhongxu[pindex]);}
}