代码随想录四刷day15

本文主要是介绍代码随想录四刷day15，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

提示：文章写完后，目录可以自动生成，如何生成可参考右边的帮助文档

文章目录

前言
一、力扣100. 相同的树
二、力扣572. 另一棵树的子树
三、力扣104. 二叉树的最大深度
四、力扣559. N 叉树的最大深度

前言

最小深度是从根节点到最近叶子节点的最短路径上的节点数量。

一、力扣100. 相同的树

递归

/*** Definition for a binary tree node.* public class TreeNode {*     int val;*     TreeNode left;*     TreeNode right;*     TreeNode() {}*     TreeNode(int val) { this.val = val; }*     TreeNode(int val, TreeNode left, TreeNode right) {*         this.val = val;*         this.left = left;*         this.right = right;*     }* }*/
class Solution {public boolean isSameTree(TreeNode p, TreeNode q) {return fun(p,q);}public boolean fun(TreeNode p, TreeNode q){if(p == null && q == null){return true;}if(p == null || q == null){return false;}if(p.val != q.val){return false;}boolean b1 = fun(p.left, q.left);boolean b2 = fun(p.right,q.right);return b1 && b2;}
}

迭代

/*** Definition for a binary tree node.* public class TreeNode {*     int val;*     TreeNode left;*     TreeNode right;*     TreeNode() {}*     TreeNode(int val) { this.val = val; }*     TreeNode(int val, TreeNode left, TreeNode right) {*         this.val = val;*         this.left = left;*         this.right = right;*     }* }*/
class Solution {public boolean isSameTree(TreeNode p, TreeNode q) {Deque<TreeNode> deq = new LinkedList<>();deq.offerLast(p);deq.offerLast(q);while(!deq.isEmpty()){TreeNode t1 = deq.pollFirst();TreeNode t2 = deq.pollFirst();if(t1 == null && t2 == null){continue;}if(t1 == null || t2 == null){return false;}if(t1.val != t2.val){return false;}deq.offerLast(t1.left);deq.offerLast(t2.left);deq.offerLast(t1.right);deq.offerLast(t2.right);}return true;}
}

二、力扣572. 另一棵树的子树

/*** Definition for a binary tree node.* public class TreeNode {*     int val;*     TreeNode left;*     TreeNode right;*     TreeNode() {}*     TreeNode(int val) { this.val = val; }*     TreeNode(int val, TreeNode left, TreeNode right) {*         this.val = val;*         this.left = left;*         this.right = right;*     }* }*/
class Solution {public boolean isSubtree(TreeNode root, TreeNode subRoot) {return postOrder(root,subRoot);}public boolean postOrder(TreeNode root, TreeNode subRoot){if(root == null){return false;}boolean b1 = postOrder(root.left,subRoot);if(b1){return b1;}boolean b2 = postOrder(root.right,subRoot);if(b2){return b2;}boolean b3 = fun(root,subRoot);return b1 || b2 || b3;}public boolean fun(TreeNode p, TreeNode q){if(p == null && q == null){return true;}if(p == null || q == null){return false;}if(p.val != q.val){return false;}boolean b1 = fun(p.left,q.left);boolean b2 = fun(p.right,q.right);return b1 && b2;}
}

三、力扣104. 二叉树的最大深度

/*** Definition for a binary tree node.* public class TreeNode {*     int val;*     TreeNode left;*     TreeNode right;*     TreeNode() {}*     TreeNode(int val) { this.val = val; }*     TreeNode(int val, TreeNode left, TreeNode right) {*         this.val = val;*         this.left = left;*         this.right = right;*     }* }*/
class Solution {public int maxDepth(TreeNode root) {return fun(root);}public int fun(TreeNode root){if(root == null){return 0;}int l = fun(root.left);int r = fun(root.right);return l > r ? l + 1 : r + 1;}
}

四、力扣559. N 叉树的最大深度

/*
// Definition for a Node.
class Node {public int val;public List<Node> children;public Node() {}public Node(int _val) {val = _val;}public Node(int _val, List<Node> _children) {val = _val;children = _children;}
};
*/class Solution {public int maxDepth(Node root) {return fun(root);}public int fun(Node root){if(root == null){return 0;}int max = 0;for(Node node : root.children){max = Math.max(max,fun(node));}return max + 1;}
}