摘要
一、二叉树原理与解题方法
二、二叉树相关算法练习题目
2.1 二叉树的深度问题
二叉树的深度_牛客题霸_牛客网
package 二叉树;
/**
* @Classname JZ55二叉树的深度
* @Description TODO
* @Date 2022/1/30 16:30
* @Created by xjl
*/
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;
}
}
102. 二叉树的层序遍历
144. 二叉树的前序遍历
94. 二叉树的中序遍历
145. 二叉树的后序遍历
从上往下打印二叉树_牛客题霸_牛客网
package 二叉树;
import java.util.*;
/**
* @Classname JZ77按之字形顺序打印二叉树
* @Description TODO
* @Date 2022/1/30 20:49
* @Created by xjl
*/
public class JZ77按之字形顺序打印二叉树 {
public class TreeNode {
int val = 0;
TreeNode left = null;
TreeNode right = null;
public TreeNode(int val) {
this.val = val;
}
}
/**
* @description 二叉树的层序遍历
* @param: pRoot
* @date: 2022/1/30 20:49
* @return: java.util.ArrayList>
* @author: xjl
*/
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;
}
/**
* @description 普通的层序遍历
* @param: pRoot
* @date: 2022/1/30 21:21
* @return: java.util.ArrayList>
* @author: xjl
*/
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;
}
/**
* @description 根 左边 右边
* @param: root
* @date: 2022/1/30 21:40
* @return: java.util.ArrayList
* @author: xjl
*/
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);
}
/**
* @description 中序遍历：左 根 右
* @param: root
* @date: 2022/1/30 21:49
* @return: java.util.List
* @author: xjl
*/
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);
}
/**
* @description 后序遍历：左 右 根
* @param: root
* @date: 2022/1/30 21:49
* @return: java.util.List
* @author: xjl
*/
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;
/**
* @Classname JZ54二叉搜索树的第k个节点
* @Description TODO
* @Date 2022/1/31 9:08
* @Created by xjl
*/
public class JZ54二叉搜索树的第k个节点 {
public class TreeNode {
int val = 0;
TreeNode left = null;
TreeNode right = null;
public TreeNode(int val) {
this.val = val;
}
}
/**
* @description TODO 这是一个二叉搜索树 那么中序遍历就是的从小到大的顺序排列的 那么
* @param: proot
* @param: k
* @date: 2022/1/31 9:08
* @return: int
* @author: xjl
*/
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);
}
}
}
剑指 Offer 07. 重建二叉树
108. 将有序数组转换为二叉搜索树
105. 从前序与中序遍历序列构造二叉树
106. 从中序与后序遍历序列构造二叉树
package 计算机程序算法分类.二叉树问题;
import 牛客网练习题.Solution;
/**
* @Classname 有序数组转变二叉搜索树108
* @Description TODO
* @Date 2021/4/30 14:09
* @Created by xjl
*/
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;
/**
* @Classname 前中序数组构造二叉树 这里是的没有的重复的数字
* @Description TODO
* @Date 2021/4/12 15:50
* @Created by xjl
*/
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;
/**
* @Classname 前中序数组构造二叉树
* @Description TODO
* @Date 2021/4/12 15:50
* @Created by xjl
*/
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);
}
/**
* @description TODO 采用的和中序和谦虚的方式是一样的
* @param: postorder
* @param: PLeft
* @param: PRight
* @param: map
* @param: inLeft
* @param: inRight
* @date: 2021/4/13 10:54
* @return: 计算机程序算法分类.dfs深度优先广度优先问题.中后序数组构造二叉树.TreeNode
* @author: xjl
*/
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;
}
}二叉树的镜像_牛客题霸_牛客网
剑指 Offer 28. 对称的二叉树
剑指 Offer 27. 二叉树的镜像
package 二叉树;
/**
* @Classname JZ27二叉树的镜像
* @Description TODO
* @Date 2022/1/30 23:42
* @Created by xjl
*/
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;
}
}
二叉树中和为某一值的路径(一)_牛客题霸_牛客网
二叉树中和为某一值的路径(二)_牛客题霸_牛客网
二叉树中和为某一值的路径(三)_牛客题霸_牛客网
package 二叉树;
import org.junit.Test;
import java.util.ArrayList;
import java.util.Deque;
import java.util.LinkedList;
/**
* @Classname JZ82二叉树中和为某一值的路径
* @Description TODO
* @Date 2022/1/30 23:43
* @Created by xjl
*/
public class JZ82二叉树中和为某一值的路径 {
public class TreeNode {
int val = 0;
TreeNode left = null;
TreeNode right = null;
public TreeNode(int val) {
this.val = val;
}
}
/**
* @description 判断能否
* @param: root
* @param: sum
* @date: 2022/1/31 15:47
* @return: boolean
* @author: xjl
*/
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();
/**
* @description 是否有路径
* @param: root
* @param: sum
* @date: 2022/1/31 15:47
* @return: boolean
* @author: xjl
*/
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);
// 为保持栈的实时性，当前节点左右子树递归完成后，总是将该节点值弹出（回溯的剪枝函数）
deque.removeLast();
}
public ArrayList FindAllPath(TreeNode root) {
addPath2(root);
return lists;
}
/**
* @description 所有的根部路径和到叶子节点的路径和
* @param: root
* @param: expectNumber
* @date: 2022/1/31 16:11
* @return: void
* @author: xjl
*/
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);
// 为保持栈的实时性，当前节点左右子树递归完成后，总是将该节点值弹出（回溯的剪枝函数）
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 二叉树;
/**
* @Classname JZ84二叉树中和为某一值的路径
* @Description TODO
* @Date 2022/1/31 17:42
* @Created by xjl
*/
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;
/**
* @description 分别计算主树 左树 右树
* @param: root
* @param: sum
* @date: 2022/1/31 17:48
* @return: int
* @author: xjl
*/
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;
}
/**
* @description 在一个树中计算目标等于的target的次数
* @param: root
* @param: sum
* @param: target
* @date: 2022/1/31 17:47
* @return: void
* @author: xjl
*/
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;
}
}
package 二叉树;
import java.util.LinkedList;
import java.util.Queue;
/**
* @Classname JZ79判断是不是平衡二叉树
* @Description TODO
* @Date 2022/1/30 23:43
* @Created by xjl
*/
public class JZ79判断是不是平衡二叉树 {
public class TreeNode {
int val = 0;
TreeNode left = null;
TreeNode right = null;
public TreeNode(int val) {
this.val = val;
}
}
/**
* @description JZ79 判断是不是平衡二叉树 左右两个子树的高度差的绝对值不超过1
* @param: null
* @date: 2022/1/31 12:15
* @return:
* @author: xjl
*/
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) 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;
}
}
对称的二叉树_牛客题霸_牛客网
剑指 Offer 28. 对称的二叉树
这不是将二叉树翻转，而是判断二叉树的左右两边是不是相同。
package 二叉树;
/**
* @Classname JZ28对称的二叉树
* @Description TODO
* @Date 2022/1/30 23:43
* @Created by xjl
*/
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);
}
/**
* @description 判断两个树是否为相同对称树的时候
* @param: L
* @param: R
* @date: 2022/1/31 11:58
* @return: boolean
* @author: xjl
*/
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);
}
}
二叉搜索树的最近公共祖先_牛客题霸_牛客网
在二叉树中找到两个节点的最近公共祖先_牛客题霸_牛客网
package 二叉树;
/**
* @Classname JZ68二叉搜索树的最近公共祖先
* @Description TODO
* @Date 2022/1/30 23:52
* @Created by xjl
*/
public class JZ68二叉搜索树的最近公共祖先 {
public class TreeNode {
int val = 0;
TreeNode left = null;
TreeNode right = null;
public TreeNode(int val) {
this.val = val;
}
}
/**
* @description 学会利用的是的二叉树的能力
* @param: root
* @param: p
* @param: q
* @date: 2022/1/31 16:27
* @return: int
* @author: xjl
*/
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 二叉树;
/**
* @Classname JZ86在二叉树中找到两个节点的最近公共祖先
* @Description TODO
* @Date 2022/1/31 16:29
* @Created by xjl
*/
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;
}
}
剑指 Offer 26. 树的子结构
面试题 04.10. 检查子树
572. 另一棵树的子树
652. 寻找重复的子树
package 二叉树;
/**
* @Classname JZ26二叉树的子树
* @Description TODO
* @Date 2022/1/30 23:18
* @Created by xjl
*/
public class JZ26二叉树的子树 {
public class TreeNode {
int val = 0;
TreeNode left = null;
TreeNode right = null;
public TreeNode(int val) {
this.val = val;
}
}
/**
* @description 判断B是A的子树 :B是A的左子树 B是A的右子树 A!=B树
* @param: root1
* @param: root2
* @date: 2022/1/31 10:09
* @return: boolean
* @author: xjl
*/
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);
}
}
543. 二叉树的直径
给定一棵二叉树，你需要计算它的直径长度。一棵二叉树的直径长度是任意两个结点路径长度中的最大值。这条路径可能穿过也可能不穿过根结点。
package 二叉树;
/**
* @Classname JZ二叉树的直径
* @Description TODO
* @Date 2022/1/31 12:55
* @Created by xjl
*/
public class JZ二叉树的直径 {
public class TreeNode {
int val;
TreeNode left;
TreeNode right;
TreeNode(int x) {
val = x;
}
}
/**
* @description TODO
* @param: root
* @date: 2022/1/31 12:55
* @return: int
* @author: xjl
*/
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;
}
}
二叉搜索树与双向链表_牛客题霸_牛客网
package 二叉树;
/**
* @Classname JZ36二叉搜索树与双向链表
* @Description TODO
* @Date 2022/2/1 16:49
* @Created by xjl
*/
public class JZ36二叉搜索树与双向链表 {
public class TreeNode {
int val = 0;
TreeNode left = null;
TreeNode right = null;
public TreeNode(int val) {
this.val = val;
}
}
/**
* @description 将二叉树进行的中序遍历，然后在将这个进行节点的生成
* @param: pRootOfTree
* @date: 2022/2/1 16:51
* @return: 二叉树.JZ36二叉搜索树与双向链表.TreeNode
* @author: xjl
*/
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);
}
}
257. 二叉树的所有路径
深度优先搜索
最直观的方法是使用深度优先搜索。在深度优先搜索遍历二叉树时，我们需要考虑当前的节点以及它的孩子节点。
- 如果当前节点不是叶子节点，则在当前的路径末尾添加该节点，并继续递归遍历该节点的每一个孩子节点。
- 如果当前节点是叶子节点，则在当前路径末尾添加该节点后我们就得到了一条从根节点到叶子节点的路径，将该路径加入到答案即可。
如此，当遍历完整棵二叉树以后我们就得到了所有从根节点到叶子节点的路径。
class Solution {
public List binaryTreePaths(TreeNode root) {
List paths = new ArrayList();
constructPaths(root, "", paths);
return paths;
}
public void constructPaths(TreeNode root, String path, List paths) {
if (root != null) {
StringBuffer pathSB = new StringBuffer(path);
pathSB.append(Integer.toString(root.val));
if (root.left == null && root.right == null) { // 当前节点是叶子节点
paths.add(pathSB.toString()); // 把路径加入到答案中
} else {
pathSB.append("->"); // 当前节点不是叶子节点，继续递归遍历
constructPaths(root.left, pathSB.toString(), paths);
constructPaths(root.right, pathSB.toString(), paths);
}
}
}
}
复杂度分析：
- 时间复杂度：O(N^2)，其中N 表示节点数目。在深度优先搜索中每个节点会被访问一次且只会被访问一次，每一次会对 path 变量进行拷贝构造，时间代价为 O(N)，故时间复杂度为O(N^2)。
- 空间复杂度：O(N2)，其中N 表示节点数目。除答案数组外我们需要考虑递归调用的栈空间。
广度优先搜索
public List paths(TreeNode root){
List paths=new ArrayList();
if (root==null){
return paths;
}
Queue nodeQueue=new ArrayDeque();
Queue pathQueue=new ArrayDeque();
nodeQueue.add(root);
pathQueue.add(Integer.toString(root.val));
while (!nodeQueue.isEmpty()){
TreeNode node=nodeQueue.poll();
String path=pathQueue.poll();
if (node.left==null&&node.right==null){
paths.add(path);
}else {
if (node.left!=null){
nodeQueue.add(node.left);
pathQueue.add(new StringBuffer(path).append("->").append(node.left.val).toString());
}
if (node.right!=null){
nodeQueue.add(node.right);
pathQueue.add(new StringBuffer(path).append("->").append(node.right.val).toString());
}
}
}
return paths;
}复杂度分析
- 时间复杂度：O(N^2)，其中N 表示节点数目。分析同方法一。
-
空间复杂度：O(N^2)，其中N 表示节点数目。在最坏情况下，队列中会存在N个节点，保存字符串的队列中每个节点的最大长度为N，故空间复杂度为O(N^2)。
《leetcode》
牛客网 - 找工作神器|笔试题库|面试经验|实习招聘内推，求职就业一站解决_牛客网
