- 浏览: 188394 次
- 性别:
- 来自: 济南
-
文章分类
最新评论
二叉树广度优先遍历我们采用队列来实现,这里列举三道leetcode中有关二叉树BFS的题目,总的思想是一样的,题目要求的输出不同,我们需要根据不同的要求来编写,考察我们对于二叉树搜索的基本思想掌握以及java基础的掌握。
1,Binary Tree Level Order Traversal
给定一颗二叉树,用广度优先搜索遍历所有节点,并输出结果。
例如:
3
/ \
9 20
/ \
15 7
输出:
[
[3],
[9,20],
[15,7]
]
这是基本的二叉树水平遍历,我们只需要借助几个变量,来辅助记录什么时候应该记录结果,什么时候遍历下一层就可以了,代码如下:
2,Binary Tree Level Order Traversal II
给定一颗二叉树,用广度优先搜索遍历所有节点,并输出结果。
例如:
3
/ \
9 20
/ \
15 7
输出:
[
[15,7],
[9,20],
[3]
]
第二道题与第一道题的输出结果不一样,是从最后一层开始的,这就考察我们对于Linkedlist的了解程度,我们用它的addFirst()方法可以轻松的将结果逆序,代码如下:
3,Binary Tree Zigzag Level Order Traversal
给定一颗二叉树,用广度优先搜索遍历所有节点,并输出结果。
例如:
3
/ \
9 20
/ \
15 7
输出:
[
[3],
[20,9],
[15,7]
]
这道题要求我们以“Z”字形来输出结果,我们可以用一个标记来记录当然的层数,如果是奇数层我们就正序添加节点到结果集中,如果是偶数层我们就逆序添加节点到结果集中,同样采用addFirst()方法,代码如下:
1,Binary Tree Level Order Traversal
给定一颗二叉树,用广度优先搜索遍历所有节点,并输出结果。
例如:
3
/ \
9 20
/ \
15 7
输出:
[
[3],
[9,20],
[15,7]
]
这是基本的二叉树水平遍历,我们只需要借助几个变量,来辅助记录什么时候应该记录结果,什么时候遍历下一层就可以了,代码如下:
/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */ public class Solution { public List<List<Integer>> levelOrder(TreeNode root) { List<List<Integer>> llist = new ArrayList<List<Integer>>(); List<Integer> list = new ArrayList<Integer>(); Queue<TreeNode> queue = new LinkedList<TreeNode>(); int count = 0; int helper = 1; if(root == null) return llist; queue.offer(root); while (!queue.isEmpty()) { TreeNode node = queue.poll(); if(helper > 0){ list.add(node.val); helper --; } if(node.left != null) { queue.offer(node.left); count ++; } if(node.right != null) { queue.offer(node.right); count ++; } if(helper == 0) { llist.add(new ArrayList<Integer>(list)); list.clear(); helper = count; count = 0; } } return llist; } }
2,Binary Tree Level Order Traversal II
给定一颗二叉树,用广度优先搜索遍历所有节点,并输出结果。
例如:
3
/ \
9 20
/ \
15 7
输出:
[
[15,7],
[9,20],
[3]
]
第二道题与第一道题的输出结果不一样,是从最后一层开始的,这就考察我们对于Linkedlist的了解程度,我们用它的addFirst()方法可以轻松的将结果逆序,代码如下:
/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */ public class Solution { public List<List<Integer>> levelOrderBottom(TreeNode root) { LinkedList<List<Integer>> llist = new LinkedList<List<Integer>>(); List<Integer> list = new ArrayList<Integer>(); Queue<TreeNode> queue = new LinkedList<TreeNode>(); if(root == null) return llist; queue.offer(root); int count = 0; int helper = 1; while(!queue.isEmpty()) { TreeNode node = queue.poll(); if(helper > 0) { list.add(node.val); helper --; } if(node.left != null) { queue.offer(node.left); count ++; } if(node.right != null) { queue.offer(node.right); count ++; } if(helper == 0) { llist.addFirst(new ArrayList<Integer>(list)); list.clear(); helper = count; count = 0; } } return llist; } }
3,Binary Tree Zigzag Level Order Traversal
给定一颗二叉树,用广度优先搜索遍历所有节点,并输出结果。
例如:
3
/ \
9 20
/ \
15 7
输出:
[
[3],
[20,9],
[15,7]
]
这道题要求我们以“Z”字形来输出结果,我们可以用一个标记来记录当然的层数,如果是奇数层我们就正序添加节点到结果集中,如果是偶数层我们就逆序添加节点到结果集中,同样采用addFirst()方法,代码如下:
/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */ public class Solution { public List<List<Integer>> zigzagLevelOrder(TreeNode root) { LinkedList<List<Integer>> llist = new LinkedList<List<Integer>>(); LinkedList<Integer> list = new LinkedList<Integer>(); Queue<TreeNode> queue = new LinkedList<TreeNode>(); int flag = 1; int count = 0; int helper = 1; if(root == null) return llist; queue.offer(root); while(!queue.isEmpty()) { TreeNode tem = queue.poll(); if(helper > 0) { if(flag % 2 == 1) { list.add(tem.val); } else { list.addFirst(tem.val); } helper --; } if(tem.left != null) { queue.offer(tem.left); count ++; } if(tem.right != null) { queue.offer(tem.right); count ++; } if(helper == 0) { llist.add(new LinkedList<Integer>(list)); helper = count; count = 0; flag ++; list.clear(); } } return llist; } }
发表评论
-
498. Diagonal Traverse
2019-11-15 13:52 288Given a matrix of M x N eleme ... -
496 Next Greater Element I
2019-11-14 13:50 292You are given two arrays (witho ... -
Word Break II
2016-03-09 03:15 413Given a string s and a dictiona ... -
Insert Interval
2016-03-08 02:11 396Given a set of non-overlapping ... -
Merge Intervals
2016-03-07 05:25 521Given a collection of intervals ... -
Merge k Sorted Lists
2016-03-07 04:03 600Merge k sorted linked lists and ... -
Multiply Strings
2016-03-06 07:27 503Given two numbers represented a ... -
N-Queens II
2016-03-06 03:06 696Follow up for N-Queens problem. ... -
N-Queens
2016-03-06 02:47 495The n-queens puzzle is the prob ... -
First Missing Positive
2016-03-05 03:09 450Given an unsorted integer array ... -
Spiral Matrix
2016-03-04 03:39 611Given a matrix of m x n element ... -
Trapping Rain Water
2016-03-04 02:54 625Given n non-negative integers r ... -
Repeated DNA Sequences
2016-03-03 03:10 451All DNA is composed of a series ... -
Increasing Triplet Subsequence
2016-03-02 02:48 924Given an unsorted array return ... -
Maximum Product of Word Lengths
2016-03-02 01:56 950Given a string array words, fin ... -
LRU Cache
2016-02-29 10:37 626Design and implement a data str ... -
Super Ugly Number
2016-02-29 07:07 715Write a program to find the nth ... -
Longest Increasing Path in a Matrix
2016-02-29 05:56 896Given an integer matrix, find t ... -
Coin Change
2016-02-29 04:39 809You are given coins of differen ... -
Minimum Height Trees
2016-02-29 04:11 749For a undirected graph with tre ...
相关推荐
LeetCode中的二叉树问题涉及到了许多经典算法,如前序遍历、中序遍历、后序遍历、层序遍历,以及各种变形题目,如求二叉树的最大深度、最小深度、判断平衡二叉树、查找二叉树的最近公共祖先等。 二叉树卡片问题通常...
1. 图论:这方面的题目涉及图的基本概念,如广度优先搜索(BFS)、深度优先搜索(DFS)、最短路径算法(例如Dijkstra或Floyd-Warshall算法)以及最大流问题(如Ford-Fulkerson或Edmonds-Karp算法)。 2. 数据结构:...
8. **二叉树**:包括中序、前序、后序遍历,层序遍历,以及各种变形问题。例如,构建二叉树、求二叉树的最大直径、最近公共祖先等。 **算法:** 1. **回溯算法**:在解决问题时,当发现当前选择无法达到目标时,会...
例如,可能会有链表的插入、删除操作,栈和队列的应用场景分析,二叉树的遍历方法(前序、中序、后序),图的深度优先搜索(DFS)和广度优先搜索(BFS)等问题。 接着,“数据结构试题B.doc”可能是另一个独立的...
12. **验证二叉查找树**:检查给定的二叉树是否符合二叉查找树的性质。可以使用递归进行验证。 13. **有效回文串**:判断一个字符串是否是回文,忽略其中的某些字符。可以使用双指针或者动态规划。 14. **单词接龙...
2. **二叉树**:二叉树题目是面试中的常客,包括前序、中序、后序遍历,查找平衡点,以及各种变形如二叉搜索树。例如,最近的节点对(Closest Binary Search Tree Value II)考察了对二叉搜索树的理解和操作。 3. *...
在挑战中,你可能需要处理各种变形的二叉树问题,如平衡二叉树、二叉搜索树或寻找特定路径。这需要熟悉递归和迭代的解题方法。 4. **图论**:虽然不是每项挑战都会涉及到图,但一旦出现,通常会是复杂度较高的题目...
- **数据测试**:几何题目中,建议多测试不对称的数据来确保算法的鲁棒性和准确性。 - **整数几何**:对于整数类型的几何计算,需关注`xmult`(坐标放大倍数)和`dmult`(距离放大倍数)是否会导致溢出。 - **浮点数...
- (poj2388, poj2299):介绍二叉树、平衡二叉树等。 3. **字符串处理**: - (poj3349, poj3274, POJ2151, poj1840, poj2002, poj2503):字符串操作算法,如哈希函数的使用、模式匹配算法等。 4. **集合和映射**...