LeetCode 二叉树题型总结
层序遍历
- 核心思路: 维护一个队列，保持队列中是本层的节点就行
- 队列中维护非null 节点
class Solution {
public List<List<Integer>> levelOrder(TreeNode root) {
Queue<TreeNode> queue = new LinkedList<>();
List<List<Integer>> ans = new ArrayList<>();
if (root==null) {
return ans;
}
queue.offer(root);
while (!queue.isEmpty()) {
int currentSize = queue.size();
List<Integer> list = new ArrayList<>();
for(int i = 0;i<currentSize;i++){
TreeNode temp = queue.poll();
list.add(temp.val);
if (temp.left!=null) {
queue.offer(temp.left);
}
if (temp.right!=null) {
queue.offer(temp.right);
}
}
ans.add(list);
}
return ans;
}
}
层序建树
/**
* 层序建树 - 使用数组（null表示空节点）
* @param arr 层序遍历的数组，null表示空节点
* @return 根节点
*/
public static TreeNode buildTree(Integer[] arr) {
if (arr == null || arr.length == 0 || arr[0] == null) {
return null;
}
// 创建根节点
TreeNode root = new TreeNode(arr[0]);
Queue<TreeNode> queue = new LinkedList<>();
queue.offer(root);
int i = 1;
while (!queue.isEmpty() && i < arr.length) {
TreeNode current = queue.poll();
// 创建左子节点
if (i < arr.length && arr[i] != null) {
current.left = new TreeNode(arr[i]);
queue.offer(current.left);
}
i++;
// 创建右子节点
if (i < arr.length && arr[i] != null) {
current.right = new TreeNode(arr[i]);
queue.offer(current.right);
}
i++;
}
return root;
}