深圳网站优化包年,黑龙江省建设会计协会网站首页,门户网站建设验收报告,网站开发 python 工具二叉树 简介[简单] 144. 二叉树的前序遍历、94. 二叉树的中序遍历、145. 二叉树的后序遍历二叉树层序遍历[中等] 102. 二叉树的层序遍历[中等] 107. 二叉树的层序遍历 II[中等] 199. 二叉树的右视图[简单] 637. 二叉树的层平均值[中等] 429. N 叉树的层序遍历[中等] 515. 在每个… 二叉树 简介[简单] 144. 二叉树的前序遍历、94. 二叉树的中序遍历、145. 二叉树的后序遍历二叉树层序遍历[中等] 102. 二叉树的层序遍历[中等] 107. 二叉树的层序遍历 II[中等] 199. 二叉树的右视图[简单] 637. 二叉树的层平均值[中等] 429. N 叉树的层序遍历[中等] 515. 在每个树行中找最大值[中等] 116. 填充每个节点的下一个右侧节点指针、[中等]117. 填充每个节点的下一个右侧节点指针 II[简单] 104. 二叉树的最大深度[简单] 111. 二叉树的最小深度 [简单] 226. 翻转二叉树[简单] 101. 对称二叉树[简单] 100. 相同的树[简单] 572. 另一棵树的子树[简单] 222. 完全二叉树的节点个数[简单] 110. 平衡二叉树[简单] 257. 二叉树的所有路径 简介
记录一下自己刷题的历程以及代码。写题过程中参考了 代码随想录的刷题路线。会附上一些个人的思路如果有错误可以在评论区提醒一下。 涉及二叉树前中后序遍历、层序遍历、队列Queue、头插法、递归、ArrayList、LinkedList、递归、StringBuilder
[简单] 144. 二叉树的前序遍历、94. 二叉树的中序遍历、145. 二叉树的后序遍历
144. 二叉树的前序遍历 94. 二叉树的中序遍历 145. 二叉树的后序遍历
前中后序遍历可以公用一套递归思路都是比较经典的模板
//先序遍历
递归访问(){对节点做操作递归访问(左子树)递归访问(右子树)
}//中序遍历
递归访问(){递归访问(左子树)对节点做操作递归访问(右子树)
}//后序遍历
递归访问(){递归访问(左子树)递归访问(右子树)对节点做操作
}二叉树的前序遍历
class Solution {public ListInteger preorderTraversal(TreeNode root) {ListInteger answer new ArrayList();preorder(root, answer);return answer;}public void preorder(TreeNode root, ListInteger answer){if(root null) return;answer.add(root.val);preorder(root.left,answer);preorder(root.right,answer);return;}
}二叉树的中序遍历
class Solution {public ListInteger inorderTraversal(TreeNode root) {ListInteger answer new ArrayList();inorder(root, answer);return answer;}public void inorder(TreeNode root, ListInteger answer){if(root null) return;inorder(root.left,answer);answer.add(root.val);inorder(root.right,answer);return;}
}二叉树的后序遍历
class Solution {public ListInteger postorderTraversal(TreeNode root) {ListInteger answer new ArrayList();postorder(root, answer);return answer;}public void postorder(TreeNode root, ListInteger answer){if(root null) return;postorder(root.left,answer);postorder(root.right,answer);answer.add(root.val);return;}
}二叉树层序遍历
[中等] 102. 二叉树的层序遍历
原题链接
经典的BFS 用队列保存树节点每次统计队列的size()也就是第n层节点数量。 处理这一层的节点将其子节点全部加入队列循环往复到队列为空。
class Solution {public ListListInteger levelOrder(TreeNode root) {ListListInteger ans new ArrayListListInteger();QueueTreeNode queue new ArrayDeque();if(root null) return ans;queue.add(root);while(!queue.isEmpty()){ListInteger nums new ArrayListInteger();int k queue.size();while(k-- 0) {TreeNode temp queue.remove();nums.add(temp.val);if (temp.left ! null) queue.add(temp.left);if (temp.right ! null) queue.add(temp.right);}ans.add(nums);}return ans;}
}[中等] 107. 二叉树的层序遍历 II
原题链接
方法① 与102的最基本的层序遍历相似的逻辑使用递归的方法把每次ans.add(nums);操作顺序进行了倒序。
class Solution {public ListListInteger levelOrderBottom(TreeNode root) {ListListInteger ans new ArrayListListInteger();QueueTreeNode queue new ArrayDeque();if(root null) return ans;queue.add(root);recursion(queue, ans);return ans;}public void recursion(QueueTreeNode queue, ListListInteger ans){if(!queue.isEmpty()){ListInteger nums new ArrayListInteger();int k queue.size();while(k-- 0) {TreeNode temp queue.remove();nums.add(temp.val);if (temp.left ! null) queue.add(temp.left);if (temp.right ! null) queue.add(temp.right);}recursion(queue, ans);ans.add(nums);}return;}
}方法② 使用LinkedList用头插法的方式构造返回值。LinkedList底层为链表头插法比较方便ArrayList底层是连续存储头插法复杂度为O(n)
class Solution {public ListListInteger levelOrderBottom(TreeNode root) {ListListInteger ans new LinkedList();QueueTreeNode queue new ArrayDeque();if(root null) return ans;queue.add(root);while(!queue.isEmpty()){ListInteger nums new ArrayListInteger();int k queue.size();while(k-- 0) {TreeNode temp queue.remove();nums.add(temp.val);if (temp.left ! null) queue.add(temp.left);if (temp.right ! null) queue.add(temp.right);}ans.add(0, nums);}return ans;}}[中等] 199. 二叉树的右视图
原题链接
与102的最基本的层序遍历相似的逻辑构建返回值时每次只把当前层最右边的数加入ans即可。
class Solution {public ListInteger rightSideView(TreeNode root) {ListInteger ans new ArrayListInteger();QueueTreeNode queue new ArrayDeque();if(root null) return ans;queue.add(root);while(!queue.isEmpty()){ListInteger nums new ArrayListInteger();int k queue.size();while(k-- 0) {TreeNode temp queue.remove();nums.add(temp.val);if (temp.left ! null) queue.add(temp.left);if (temp.right ! null) queue.add(temp.right);}ans.add((nums.get(nums.size()-1)));}return ans;}
}
[简单] 637. 二叉树的层平均值
原题链接
class Solution {public ListDouble averageOfLevels(TreeNode root) {QueueTreeNode queue new ArrayDeque();ListDouble ans new ArrayList();if(root null) return ans;queue.add(root);while(!queue.isEmpty()){double num 0;int k queue.size();int i k;while(k-- 0){TreeNode temp queue.remove();num temp.val;if(temp.left ! null) queue.add(temp.left);if(temp.right ! null) queue.add(temp.right);}ans.add(num / i);}return ans;}
}[中等] 429. N 叉树的层序遍历
原题链接
class Solution {public ListListInteger levelOrder(Node root) {ListListInteger ans new ArrayListListInteger();QueueNode queue new ArrayDeque();if(root null) return ans;queue.add(root);while(!queue.isEmpty()){ListInteger nums new ArrayListInteger();int k queue.size();while(k-- 0) {Node temp queue.remove();nums.add(temp.val);for(int i 0; i temp.children.size(); i) {queue.add(temp.children.get(i));}}ans.add(nums);}return ans;}
}[中等] 515. 在每个树行中找最大值
原题链接
class Solution {public ListInteger largestValues(TreeNode root) {ListInteger ans new ArrayList();QueueTreeNode queue new ArrayDeque();if(root null) return ans;queue.add(root);while(!queue.isEmpty()){int max queue.peek().val;int k queue.size();while(k-- 0) {TreeNode temp queue.remove();max max temp.val ? max : temp.val;if(temp.left ! null) queue.add(temp.left);if(temp.right ! null) queue.add(temp.right);}ans.add(max);}return ans;}
}[中等] 116. 填充每个节点的下一个右侧节点指针、[中等]117. 填充每个节点的下一个右侧节点指针 II
[中等] 116. 填充每个节点的下一个右侧节点指针 [中等]117. 填充每个节点的下一个右侧节点指针 II 方法① 正常的层序遍历每层除了最后一个节点之外都对next赋值
class Solution {public Node connect(Node root) {ListInteger ans new ArrayList();QueueNode queue new ArrayDeque();if(root null) return root;queue.add(root);while(!queue.isEmpty()){int k queue.size();while(k-- 0) {Node temp queue.remove();if(k 0) {temp.next queue.peek();}if(temp.left ! null) queue.add(temp.left);if(temp.right ! null) queue.add(temp.right);}}return root;}
}方法② 使用next链接来对同层次节点做遍历可以省去队列的开销 注意Node引用需要申请在方法外不能做参数传递java中都是值传递
class Solution {Node last null, nextStart null;public Node connect(Node root) {ListInteger ans new ArrayList();if(root null) return root;Node p root;while(p!null){if(p.left ! null){handle(p.left);}if(p.right ! null){handle(p.right);}p p.next;if(p null nextStart ! null){p nextStart;nextStart null;last null;}}return root;}public void handle(Node p){if(nextStart null){nextStart p;}if(last ! null){last.next p;}last p;}}[简单] 104. 二叉树的最大深度
原题链接
方法①层序遍历
class Solution {public int maxDepth(TreeNode root) {int depth 0;if(root null) return depth;QueueTreeNode queue new ArrayDeque();queue.add(root);while(!queue.isEmpty()){depth;int k queue.size();while(k-- 0) {TreeNode temp queue.remove();if (temp.left ! null) queue.add(temp.left);if (temp.right ! null) queue.add(temp.right);}}return depth;}
}方法②递归 树的高度就是 其子树的最大高度 1用在多叉树上也是一样的思路
class Solution {public int maxDepth(TreeNode root) {if(root null) return 0;int leftDepth maxDepth(root.left);int rightDepth maxDepth(root.right);return (leftDepth rightDepth ? leftDepth : rightDepth) 1;}
}[简单] 111. 二叉树的最小深度
原题链接 方法①层序遍历找左右子树皆空的点即可
class Solution {public int minDepth(TreeNode root) {int depth 0;if(root null) return depth;QueueTreeNode queue new ArrayDeque();queue.add(root);while(!queue.isEmpty()){depth;int k queue.size();while(k-- 0) {TreeNode temp queue.remove();if(temp.left null temp.right null) return depth;if (temp.left ! null) queue.add(temp.left);if (temp.right ! null) queue.add(temp.right);}}return depth;}
}方法②递归求解 用递归求解记住需要的是到叶子节点的深度 如果非叶子节点假设只有单边左子树右子数应当是找不到叶子节点也就是距离无穷大可以设置一个Integer.MAX_VALUE做为返回值这样通过比较递归的上一层就会获得左子树找到叶子节点的最小距离 1
class Solution {public int minDepth(TreeNode root) {if(root null) return 0;if(root.left null root.right null) return 1;int leftMin Integer.MAX_VALUE;int rightMin Integer.MAX_VALUE;if(root.left ! null) leftMin minDepth(root.left);if(root.right ! null) rightMin minDepth(root.right);return (leftMin rightMin ? leftMin : rightMin) 1;}
}[简单] 226. 翻转二叉树
原题链接
前序遍历的基础上每一次遍历节点做翻转操作。 切记前序、后续、层次遍历都可以但是不可以是中序遍历因为中序遍历是左 中 右 的顺序递归调整左子树之后处理当前节点会把左右子树对调这样进入右子数递归时其实还是对原先的左子树做操作。
class Solution {public TreeNode invertTree(TreeNode root) {preorder(root);return root;}public void preorder(TreeNode root){if(root null) return;TreeNode temp root.left;root.left root.right;root.right temp;preorder(root.left);preorder(root.right);return;}
}[简单] 101. 对称二叉树
原题链接
经典的递归思路对左右子树做反方向的递归即可在左子树上做前序遍历每次递归left的左节点时就去递归right的右节点递归left的右节点时则递归right的左节点。
class Solution {public boolean isSymmetric(TreeNode root) {if(root null) return true;TreeNode left root.left;TreeNode right root.right;return recursion(left, right);}public boolean recursion(TreeNode left, TreeNode right){if(left null right null)return true;else if(left ! null right ! null) {if (left.val ! right.val)return false;if (recursion(left.left, right.right) recursion(left.right, right.left))return true;}return false;}
}[简单] 100. 相同的树
原题链接
两棵树同频做前序遍历即可其他遍历方式也是ok的。
class Solution {public boolean isSameTree(TreeNode p, TreeNode q) {return recursion(p, q);}public boolean recursion(TreeNode p, TreeNode q){if(p null q null)return true;else if(p ! null q ! null) {if (p.val ! q.val)return false;if (recursion(p.left, q.left) recursion(p.right, q.right))return true;}return false;}
}[简单] 572. 另一棵树的子树
原题链接
两层递归 ①preorder对root 的前序遍历找到与subRoot相同值的节点作为比较的起点②cmprecursion对root的节点以及subRoot的根节点 做 同频前序遍历对比
class Solution {public boolean isSubtree(TreeNode root, TreeNode subRoot) {if(subRoot null) return true;if(root null) return true;return preorder(root, subRoot);}public boolean preorder(TreeNode p, TreeNode q){if(p null) return false;if(p.val q.val cmprecursion(p, q))return true;if(preorder(p.left, q) || preorder(p.right, q)) return true;return false;}public boolean cmprecursion(TreeNode p, TreeNode q){if(p null q null) return true;else if(p ! null q ! null){if(p.val ! q.val) return false;if(cmprecursion(p.left, q.left) cmprecursion(p.right, q.right))return true;}return false;}
}[简单] 222. 完全二叉树的节点个数
原题链接
递归
class Solution {public int countNodes(TreeNode root) {if(root null) return 0;return countNodes(root.left) countNodes(root.right) 1;}
}[简单] 110. 平衡二叉树
原题链接
递归后序遍历 用-2标记 以当前节点为根节点的子树非平衡二叉树在递归中一旦出现-2就层层传递到root用来标识存在子树为非平衡二叉树
class Solution {public boolean isBalanced(TreeNode root) {if(countDepth(root) -2) return false;return true;}public int countDepth(TreeNode p){if(p null) return 0;int leftDepth countDepth(p.left);int rightDepth countDepth(p.right);int flag leftDepth - rightDepth;if(leftDepth -2 || rightDepth -2 || flag 1 || flag -1) return -2;else return (leftDepth rightDepth ? leftDepth : rightDepth) 1;}
}[简单] 257. 二叉树的所有路径
原题链接
思路就是DFS深度优先遍历找到每一条路径效率差异主要体现在对字符串拼接的处理上使用StringBuilder会更高效一些。
class Solution {public ListString binaryTreePaths(TreeNode root) {ListString ans new ArrayList();if(root null) return ans;DFS(root, ans, );return ans;}public void DFS(TreeNode p, ListString ans, String string){StringBuilder sb new StringBuilder(string);sb.append(p.val);if(p.left null p.right null){ans.add(sb.toString());return;}sb.append(-);if(p.left ! null)DFS(p.left, ans, sb.toString());if(p.right ! null)DFS(p.right, ans, sb.toString());}
}
