二叉树的深度_牛客题霸_牛客网
package 二叉树;
public class JZ55二叉树的深度 {
public class TreeNode {
int val;
TreeNode left;
TreeNode right;
public TreeNode(int val) {
this.val = val;
}
}
public int TreeDepth(TreeNode root) {
if (root==null){
return 0;
}
int deep = TreeDepthlen(root);
return deep;
}
public int TreeDepthlen(TreeNode root) {
if (root==null){
return 0;
}
int llen=TreeDepth(root.left);
int rlen=TreeDepth(root.right);
return llen>rlen?llen+1:rlen+1;
}
}
2.2 二叉树的遍历问题
102. 二叉树的层序遍历
144. 二叉树的前序遍历
94. 二叉树的中序遍历
145. 二叉树的后序遍历
从上往下打印二叉树_牛客题霸_牛客网
package 二叉树;
import java.util.*;
public class JZ77按之字形顺序打印二叉树 {
public class TreeNode {
int val = 0;
TreeNode left = null;
TreeNode right = null;
public TreeNode(int val) {
this.val = val;
}
}
public ArrayList> Print(TreeNode pRoot) {
if (pRoot == null) {
return new ArrayList>();
}
ArrayList> lists = new ArrayList>();
Queue queue = new linkedList();
queue.add(pRoot);
int index = 1;
while (!queue.isEmpty()) {
int number = queue.size();
ArrayList list = new ArrayList();
while (number != 0) {
TreeNode node = queue.poll();
if (node.left != null) {
queue.add(node.left);
}
if (node.right != null) {
queue.add(node.right);
}
list.add(node.val);
number--;
}
if (index % 2 == 0) {
Collections.reverse(list);
}
lists.add(list);
index++;
}
return lists;
}
public ArrayList> Print2(TreeNode pRoot) {
if (pRoot == null) {
return new ArrayList>();
}
ArrayList> lists = new ArrayList>();
Queue queue = new linkedList();
queue.add(pRoot);
while (!queue.isEmpty()) {
ArrayList list = new ArrayList();
int number = queue.size();
while (number != 0) {
TreeNode node = queue.poll();
if (node.left != null) {
queue.add(node.left);
}
if (node.right != null) {
queue.add(node.right);
}
list.add(node.val);
number--;
}
lists.add(list);
}
return lists;
}
public List> Print3(TreeNode pRoot) {
if (pRoot == null) {
return new ArrayList>();
}
List> lists = new ArrayList>();
Queue queue = new linkedList();
queue.add(pRoot);
while (!queue.isEmpty()) {
ArrayList list = new ArrayList();
int number = queue.size();
while (number != 0) {
TreeNode node = queue.poll();
if (node.left != null) {
queue.add(node.left);
}
if (node.right != null) {
queue.add(node.right);
}
list.add(node.val);
number--;
}
lists.add(list);
}
return lists;
}
public ArrayList PrintFromTopToBottom(TreeNode pRoot) {
if (pRoot == null) {
return new ArrayList();
}
ArrayList list = new ArrayList();
Queue queue = new linkedList();
queue.add(pRoot);
while (!queue.isEmpty()) {
int number = queue.size();
while (number != 0) {
TreeNode node = queue.poll();
if (node.left != null) {
queue.add(node.left);
}
if (node.right != null) {
queue.add(node.right);
}
list.add(node.val);
number--;
}
}
return list;
}
public List preorderTraversal(TreeNode root) {
List res = new ArrayList();
preorder(root, res);
return res;
}
private void preorder(TreeNode root, List res) {
if (root == null) {
return;
}
res.add(root.val);
preorder(root.left, res);
preorder(root.right, res);
}
public List middleTraversal(TreeNode root) {
List res = new ArrayList();
middle(root, res);
return res;
}
private void middle(TreeNode root, List res) {
if (root == null) {
return;
}
middle(root.left, res);
res.add(root.val);
middle(root.right, res);
}
public List afterTraversal(TreeNode root) {
List res = new ArrayList();
after(root, res);
return res;
}
private void after(TreeNode root, List res) {
if (root == null) {
return;
}
after(root.left, res);
after(root.right, res);
res.add(root.val);
}
}
二叉搜索树的第k个节点_牛客题霸_牛客网
package 二叉树;
import org.junit.Test;
import java.util.ArrayList;
import java.util.List;
public class JZ54二叉搜索树的第k个节点 {
public class TreeNode {
int val = 0;
TreeNode left = null;
TreeNode right = null;
public TreeNode(int val) {
this.val = val;
}
}
public int KthNode(TreeNode proot, int k) {
if (proot == null) {
return -1;
}
ArrayList list = new ArrayList();
middle(proot, list);
if (list.size() < k || k == 0) {
return -1;
} else {
return list.get(k - 1);
}
}
public void middle(TreeNode proot, ArrayList list) {
if (proot == null) {
return;
}
if (proot.left != null) {
middle(proot.left, list);
}
list.add(proot.val);
if (proot.right != null) {
middle(proot.right, list);
}
}
int ans=Integer.MIN_VALUE;
int index=0;
public int KthNode2(TreeNode proot, int k) {
if (proot == null||k == 0) {
return -1;
}
middle2(proot,k);
if (ans==Integer.MIN_VALUE){
return -1;
}else {
return ans;
}
}
public void middle2(TreeNode proot,int k) {
if (proot == null) {
return;
}
if (proot.left != null) {
middle2(proot.left,k);
}
index++;
if (index==k){
ans=proot.val;
}
if (proot.right != null) {
middle2(proot.right,k);
}
}
}
2.3 重建二叉树问题
剑指 Offer 07. 重建二叉树
108. 将有序数组转换为二叉搜索树
105. 从前序与中序遍历序列构造二叉树
106. 从中序与后序遍历序列构造二叉树
package 计算机程序算法分类.二叉树问题;
import 牛客网练习题.Solution;
public class 有序数组转变二叉搜索树108 {
public class TreeNode {
int val;
TreeNode left;
TreeNode right;
public TreeNode(int val) {
this.val = val;
}
}
public TreeNode sortedArrayToBST(int[] nums) {
return helper(nums, 0, nums.length - 1);
}
public TreeNode helper(int[] nums, int left, int right) {
if (left > right) {
return null;
}
// 总是选择中间位置左边的数字作为根节点
int mid = (left + right) / 2;
TreeNode root = new TreeNode(nums[mid]);
root.left = helper(nums, left, mid - 1);
root.right = helper(nums, mid + 1, right);
return root;
}
public TreeNode sortedArrayToBSTTest(int[] nums) {
return buidtree(nums, 0, nums.length - 1);
}
private TreeNode buidtree(int[] nums, int left, int right) {
if (left > right) {
return null;
}
int mid = left + (right - left) / 2;
TreeNode node = new TreeNode(nums[mid]);
node.left = buidtree(nums, left, mid - 1);
node.right = buidtree(nums, mid + 1, right);
return node;
}
}
package 计算机程序算法分类.dfs深度优先广度优先问题;
import java.util.HashMap;
import java.util.Map;
public class 前中序数组构造二叉树 {
public class TreeNode {
int val;
TreeNode left;
TreeNode right;
public TreeNode(int val) {
this.val = val;
}
}
public TreeNode buildTree(int[] preorder, int[] inorder) {
int preLen = preorder.length;
int inLen = inorder.length;
if (preLen != inLen) {
throw new RuntimeException("Incorrect input data.");
}
//存储中序遍历的值
Map map = new HashMap<>();
for (int i = 0; i < inLen; i++) {
map.put(inorder[i], i);
}
return buildTreedfs(preorder, 0, preLen - 1, map, 0, inLen - 1);
}
private TreeNode buildTreedfs(int[] preorder, int preLeft, int preRight, Map map, int inLeft, int inRight) {
if (preLeft > preRight || inLeft > inRight) {
return null;
}
int rootval = preorder[preLeft];
//简历根节点
TreeNode root = new TreeNode(rootval);
int pIndex = map.get(rootval);
//构造左子树
root.left = buildTreedfs(preorder, preLeft + 1, pIndex - inLeft + preLeft, map, inLeft, pIndex - 1);
//构造右子树
root.right = buildTreedfs(preorder, pIndex - inLeft + preLeft + 1, preRight, map, pIndex + 1, inRight);
return root;
}
}
package 计算机程序算法分类.dfs深度优先广度优先问题;
import java.util.HashMap;
import java.util.Map;
public class 中后序数组构造二叉树 {
public class TreeNode {
int val;
TreeNode left;
TreeNode right;
public TreeNode(int val) {
this.val = val;
}
}
public TreeNode buildTree(int[] inorder, int[] postorder) {
int inLen = inorder.length - 1;
int poLen = postorder.length - 1;
if (inLen != poLen) {
return null;
}
Map map = new HashMap<>();
for (int i = 0; i < inorder.length; i++) {
map.put(inorder[i], i);
}
return dfs(postorder, 0, poLen, map, 0, inLen);
}
private TreeNode dfs(int[] postorder, int PLeft, int PRight, Map map, int inLeft, int inRight) {
if (PLeft > PRight || inLeft > inRight) {
return null;
}
int rootval = postorder[PRight];
TreeNode root = new TreeNode(rootval);
int Index = map.get(rootval);
root.left = dfs(postorder, PLeft, Index + PLeft-inLeft- 1, map, inLeft, Index - 1);
root.right = dfs(postorder, Index + PLeft-inLeft, PRight - 1, map, Index + 1, inRight);
return root;
}
}
2.4 二叉树的镜像问题
二叉树的镜像_牛客题霸_牛客网
剑指 Offer 28. 对称的二叉树
剑指 Offer 27. 二叉树的镜像
package 二叉树;
public class JZ27二叉树的镜像 {
public class TreeNode {
int val = 0;
TreeNode left = null;
TreeNode right = null;
public TreeNode(int val) {
this.val = val;
}
}
public TreeNode Mirror(TreeNode pRoot) {
if (pRoot == null) return pRoot;
if (pRoot.left == null && pRoot.right == null) {
return pRoot;
}
//处理根节点，交换左右节点
TreeNode temp = pRoot.left;
pRoot.left = pRoot.right;
pRoot.right = temp;
//处理左子树
Mirror(pRoot.left);
//处理右子树
Mirror(pRoot.right);
return pRoot;
}
public TreeNode Mirror2(TreeNode pRoot) {
if (pRoot == null || (pRoot.left == null && pRoot.right == null)) {
return pRoot;
}
TreeNode tmp = pRoot.left;
pRoot.left= pRoot.right;
pRoot.right = tmp;
Mirror2(pRoot.left);
Mirror2(pRoot.right);
return pRoot;
}
}
2.5 二叉树的路径和问题
二叉树中和为某一值的路径(一)_牛客题霸_牛客网
二叉树中和为某一值的路径(二)_牛客题霸_牛客网
二叉树中和为某一值的路径(三)_牛客题霸_牛客网
package 二叉树;
import org.junit.Test;
import java.util.ArrayList;
import java.util.Deque;
import java.util.linkedList;
public class JZ82二叉树中和为某一值的路径 {
public class TreeNode {
int val = 0;
TreeNode left = null;
TreeNode right = null;
public TreeNode(int val) {
this.val = val;
}
}
public boolean hasPathSum(TreeNode root, int sum) {
if (root == null) {
return false;
}
if (root.left == null && root.right == null) {
return sum - root.val == 0;
}
boolean res1 = hasPathSum(root.left, sum - root.val);
boolean res2 = hasPathSum(root.right, sum - root.val);
return res1 || res2;
}
// 定义全局arr减少参数
ArrayList> lists = new ArrayList>();
// 用栈作为模板，实时记录
Deque deque = new linkedList();
public ArrayList> FindPath(TreeNode root, int expectNumber) {
addPath(root, expectNumber);
return lists;
}
public void addPath(TreeNode root, int expectNumber) {
// 判空
if (root == null) {
return;
}
// 每遍历到一个结点，先入队
deque.addLast(root.val);
// 如果左右节点为空时，sum-val恰好=0，说明找到一条路径，立即以当前deque为模板, 创建新链表加入ret
if (root.left == null && root.right == null && expectNumber - root.val == 0) {
lists.add(new ArrayList(deque));
}
// 左右子树递归
addPath(root.left, expectNumber - root.val);
addPath(root.right, expectNumber - root.val);
// 为保持栈的实时性，当前节点左右子树递归完成后，总是将该节点值d出（回溯的剪枝函数）
deque.removeLast();
}
public ArrayList> FindAllPath(TreeNode root) {
addPath2(root);
return lists;
}
public void addPath2(TreeNode root) {
// 判空
if (root == null) {
return;
}
// 每遍历到一个结点，先入队
deque.addLast(root.val);
// 如果左右节点为空时，sum-val恰好=0，说明找到一条路径，立即以当前deque为模板, 创建新链表加入ret
if (root.left == null && root.right == null) {
lists.add(new ArrayList(deque));
}
// 左右子树递归
addPath2(root.left);
addPath2(root.right);
// 为保持栈的实时性，当前节点左右子树递归完成后，总是将该节点值d出（回溯的剪枝函数）
deque.removeLast();
}
@Test
public void test() {
TreeNode root = new TreeNode(1);
TreeNode node1 = new TreeNode(2);
TreeNode node2 = new TreeNode(3);
TreeNode node3 = new TreeNode(4);
TreeNode node4 = new TreeNode(5);
TreeNode node5 = new TreeNode(6);
TreeNode node6 = new TreeNode(7);
root.left = node1;
root.right = node2;
node1.left = node3;
node1.right = node4;
node2.left = node5;
node2.right = node6;
ArrayList> lists = FindAllPath(root);
for (ArrayList list : lists) {
for (Integer i : list) {
System.out.print(i + "");
}
System.out.println();
}
}
}
package 二叉树;
public class JZ84二叉树中和为某一值的路径 {
public class TreeNode {
int val = 0;
TreeNode left = null;
TreeNode right = null;
public TreeNode(int val) {
this.val = val;
}
}
private int ans;
public int FindPath(TreeNode root, int sum) {
if (root == null) {
return 0;
}
dfs(root, sum, 0);
FindPath(root.left, sum);
FindPath(root.right, sum);
return ans;
}
public void dfs(TreeNode root, int sum, int target) {
if (root == null) {
return ;
}
target += root.val;
if (target == sum) {
ans ++;
}
dfs(root.left, sum, target);
dfs(root.right, sum, target);
target -= root.val;
}
}
2.6 平衡二叉树问题
package 二叉树;
import java.util.linkedList;
import java.util.Queue;
public class JZ79判断是不是平衡二叉树 {
public class TreeNode {
int val = 0;
TreeNode left = null;
TreeNode right = null;
public TreeNode(int val) {
this.val = val;
}
}
public boolean IsBalanced_Solution(TreeNode root) {
if (root == null) {
return true;
}
int L = TreeDepth(root.left);
int R = TreeDepth(root.right);
return Math.abs(L - R) <= 1 && IsBalanced_Solution(root.left) && IsBalanced_Solution(root.right);
}
private int TreeDepth(TreeNode root) {
if (root == null) {
return 0;
}
int llen = TreeDepth(root.left);
int rlen = TreeDepth(root.right);
return llen > rlen ? llen + 1 : rlen + 1;
}
public int maxDepth(TreeNode root) {
//1.层次遍历
if (root == null) {
return 0;
}
Queue queue = new linkedList();
queue.add(root);
int res = 0;
while (!queue.isEmpty()) {
int n = queue.size();
res++;
for (int i = 0; i < n; i++) {
TreeNode cur = queue.poll();
if (cur.left != null) {
queue.add(cur.left);
}
if (cur.right != null) {
queue.add(cur.right);
}
}
}
return res;
}
}
2.7 对称二叉树问题
对称的二叉树_牛客题霸_牛客网
剑指 Offer 28. 对称的二叉树
这不是将二叉树翻转，而是判断二叉树的左右两边是不是相同。
package 二叉树;
public class JZ28对称的二叉树 {
public class TreeNode {
int val;
TreeNode left;
TreeNode right;
TreeNode(int x) {
val = x;
}
}
public boolean isSymmetric(TreeNode root) {
return root == null ? true : recur(root.left, root.right);
}
boolean recur(TreeNode L, TreeNode R) {
if (L == null && R == null) return true;
if (L == null || R == null || L.val != R.val) return false;
return recur(L.left, R.right) && recur(L.right, R.left);
}
}
2.8 二叉树公共祖先问题
二叉搜索树的最近公共祖先_牛客题霸_牛客网
在二叉树中找到两个节点的最近公共祖先_牛客题霸_牛客网
package 二叉树;
public class JZ68二叉搜索树的最近公共祖先 {
public class TreeNode {
int val = 0;
TreeNode left = null;
TreeNode right = null;
public TreeNode(int val) {
this.val = val;
}
}
public int lowestCommonAncestor(TreeNode root, int p, int q) {
// 随便给2个数，利用二叉搜索树的性质：
// 如果两个值都小于根节点，说明祖先在左子树一侧
if (p < root.val && q < root.val)
return lowestCommonAncestor(root.left, p, q);
// 如果两个值都大于根节点，说明祖先在右子树一侧
if (p > root.val && q > root.val)
return lowestCommonAncestor(root.right, p, q);
// 剩最后一种情况：如果根节点的值恰好在两个给定值之间，这个根节点就是最近的公共祖先
return root.val;
}
}
package 二叉树;
public class JZ86在二叉树中找到两个节点的最近公共祖先 {
public class TreeNode {
int val = 0;
TreeNode left = null;
TreeNode right = null;
public TreeNode(int val) {
this.val = val;
}
}
public int lowestCommonAncestor(TreeNode root, int p, int q) {
TreeNode treeNode = lowestCommonAncestor(root, new TreeNode(p), new TreeNode(q));
return treeNode.val;
}
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
if (root == null) {
return root;
}
//当两个值扥等于root的时候
if (root.val == p.val || root.val == q.val) {
return root;
}
//当不等于root的时候 这个时候需要的递归
TreeNode left = lowestCommonAncestor(root.left, p, q);
TreeNode right = lowestCommonAncestor(root.right, p, q);
if (left != null && right != null) {
return root;
}
if (left == null) {
return right;
}
if (right == null) {
return left;
}
return null;
}
}
2.9 二叉树的子树问题
剑指 Offer 26. 树的子结构
面试题 04.10. 检查子树
572. 另一棵树的子树
652. 寻找重复的子树
package 二叉树;
public class JZ26二叉树的子树 {
public class TreeNode {
int val = 0;
TreeNode left = null;
TreeNode right = null;
public TreeNode(int val) {
this.val = val;
}
}
public boolean HasSubtree(TreeNode root1, TreeNode root2) {
boolean result = false;
//当Tree1和Tree2都不为零的时候，才进行比较。否则直接返回false
if (root2 != null && root1 != null) {
//如果找到了对应Tree2的根节点的点
if (root1.val == root2.val) {
//以这个根节点为为起点判断是否包含Tree2
result = doesTree1HaveTree2(root1, root2);
}
//如果找不到，那么就再去root的左儿子当作起点，去判断时候包含Tree2
if (!result) {
result = HasSubtree(root1.left, root2);
}
//如果还找不到，那么就再去root的右儿子当作起点，去判断时候包含Tree2
if (!result) {
result = HasSubtree(root1.right, root2);
}
}
//返回结果
return result;
}
//判断两个树是否相同
public static boolean doesTree1HaveTree2(TreeNode node1, TreeNode node2) {
//如果Tree2已经遍历完了都能对应的上，返回true
if (node2 == null) {
return true;
}
//如果Tree2还没有遍历完，Tree1却遍历完了。返回false
if (node1 == null) {
return false;
}
//如果其中有一个点没有对应上，返回false
if (node1.val != node2.val) {
return false;
}
//如果根节点对应的上，那么就分别去子节点里面匹配
return doesTree1HaveTree2(node1.left, node2.left) && doesTree1HaveTree2(node1.right, node2.right);
}
//方法一：递归的方式（利用深度优先遍历的思想）
public boolean HasSubtree1(TreeNode root1,TreeNode root2) {
//判断root1和root2是否为null（空树不是任意一个树的子结构）
if(root1 == null || root2 == null) return false;
//如果首结点不相等，则依次比较左子树、右子树与root2的关系
return isSame(root1, root2) || HasSubtree1(root1.left, root2) || HasSubtree1(root1.right,root2);
}
//首先：判断结构相同必须需要的函数
public boolean isSame(TreeNode root1,TreeNode root2){
//如果root2为空，则为true（不需要考虑root1的状况）
if(root2 == null) return true;
if(root1 == null) return false;
return root1.val == root2.val && isSame(root1.left, root2.left) && isSame(root1.right, root2.right);
}
}
2.10 二叉树最长直径问题
543. 二叉树的直径
给定一棵二叉树，你需要计算它的直径长度。一棵二叉树的直径长度是任意两个结点路径长度中的最大值。这条路径可能穿过也可能不穿过根结点。
package 二叉树;
public class JZ二叉树的直径 {
public class TreeNode {
int val;
TreeNode left;
TreeNode right;
TreeNode(int x) {
val = x;
}
}
int len = 0;
public int diameterOfBinaryTree(TreeNode root) {
if (root == null) {
return 0;
}
deep(root);
return len;
}
private int deep(TreeNode root) {
if (root == null) {
return 0;
}
int L = deep(root.left);
int R = deep(root.right);
len = Math.max(len, L + R);// 计算d_node即L+R+1 并更新ans
return Math.max(L, R) + 1;
}
}
2.11 二叉搜索树与双向链表
二叉搜索树与双向链表_牛客题霸_牛客网
package 二叉树;
public class JZ36二叉搜索树与双向链表 {
public class TreeNode {
int val = 0;
TreeNode left = null;
TreeNode right = null;
public TreeNode(int val) {
this.val = val;
}
}
TreeNode res = null;
public TreeNode Convert(TreeNode pRootOfTree) {
if (pRootOfTree == null) {
return pRootOfTree;
}
Convert(pRootOfTree.right);
if (res == null) {
res = pRootOfTree;
} else {
res.left = pRootOfTree;
pRootOfTree.right = res;
res = pRootOfTree;
}
Convert(pRootOfTree.left);
return res;
}
private TreeNode pre;
private TreeNode head;
public TreeNode Convert2(TreeNode pRootOfTree) {
if (pRootOfTree == null) {
return null;
}
dfs(pRootOfTree);
head.left = pre;
pre.right = head;
return head;
}
public void dfs(TreeNode current) {
if (current == null) {
return;
}
dfs(current.left);
current.left = pre;
if (pre == null) {
head = current;
} else {
pre.right = current;
}
pre = current;
dfs(current.right);
}
}
博文参考
牛客网 - 找工作神器|笔试题库|面试经验|实习招聘内推，求职就业一站解决_牛客网
欢迎分享，转载请注明来源：内存溢出
微信扫一扫
支付宝扫一扫
评论列表（0条）