二叉树的镜像
请完成一个函数，输入一个二叉树，该函数输出它的镜像。
例如输入：
4
/ \
2 7
/ \ / \
1 3 6 9
镜像输出：
4
/ \
7 2
/ \ / \
9 6 3 1
示例 1：
输入：root = [4,2,7,1,3,6,9]
输出：[4,7,2,9,6,3,1]
递归：
public TreeNode mirrorTree(TreeNode root) {
if(root==null){
return null;
}
TreeNode temp=root.left;
root.left=mirrorTree(root.right);
root.right=mirrorTree(temp);
return root;
}
非递归：
public TreeNode mirrorTree(TreeNode root) {
Stack<TreeNode> stack=new Stack();
stack.push(root);
while(!stack.isEmpty()){
TreeNode node=stack.pop();
if(node!=null){
TreeNode temp=node.left;
node.left=node.right;
node.right=temp;
stack.push(node.left);
stack.push(node.right);
}
}
return root;
}
二叉树的序列化与反序列化
序列化是将一个数据结构或者对象转换为连续的比特位的操作，进而可以将转换后的数据存储在一个文件或者内存中，同时也可以通过网络传输到另一个计算机环境，采取相反方式重构得到原数据。
请设计一个算法来实现二叉树的序列化与反序列化。这里不限定你的序列 / 反序列化算法执行逻辑，你只需要保证一个二叉树可以被序列化为一个字符串并且将这个字符串反序列化为原始的树结构。
示例:
你可以将以下二叉树：
1
/ \
2 3
/ \
4 5
序列化为 "[1,2,3,null,null,4,5]"
说明:不要使用类的成员 / 全局 / 静态变量来存储状态，你的序列化和反序列化算法应该是无状态的
方法一：先序遍历
class Codec {
// Encodes a tree to a single string.
public String serialize(TreeNode root) {
StringBuilder sb = new StringBuilder();
preorder(root, sb);
return sb.toString().trim();
}
private int index;
// Decodes your encoded data to tree.
public TreeNode deserialize(String data) {
String[] splits = data.split(" ");
index = 0;
return construct(splits);
}
public TreeNode construct(String[] splits) {
if (splits[index].equals("null")) {
index++;
return null;
}】
TreeNode root = new TreeNode(Integer.valueOf(splits[index]));
index++;
root.left = construct(splits);
root.right = construct(splits);
return root;
}
public void preorder(TreeNode root, StringBuilder sb) {
if (root == null) {
sb.append("null ");
} else {
sb.append(root.val).append(" ");
preorder(root.left, sb);
preorder(root.right, sb);
}
}
}
方法二：层次遍历
class Codec {
// Encodes a tree to a single string.
public String serialize(TreeNode root) {
if (root == null) {
return "null";
}
StringBuilder sb = new StringBuilder();
Queue<TreeNode> queue = new LinkedList<>();
queue.offer(root);
while (!queue.isEmpty()) {
TreeNode node = queue.poll();
if (node != null) {
queue.offer(node.left);
queue.offer(node.right);
sb.append(node.val).append(" ");
} else {
sb.append("null ");
}
}
return sb.toString().trim();
}
// Decodes your encoded data to tree.
public TreeNode deserialize(String data) {
String[] splits = data.split(" ");
if (splits.length == 1) {
return null;
}
TreeNode root = new TreeNode(Integer.valueOf(splits[0]));
Queue<TreeNode> queue = new LinkedList<>();
queue.offer(root);
int index = 1;
while (!queue.isEmpty()) {
TreeNode node = queue.poll();
if (!splits[index].equals("null")) {
TreeNode left = new TreeNode(Integer.valueOf(splits[index]));
queue.offer(left);
node.left = left;
}
index++;
if (!splits[index].equals("null")) {
TreeNode right = new TreeNode(Integer.valueOf(splits[index]));
queue.offer(right);
node.right = right;
}
index++;
}
return root;
}
}
二叉树的右视图
给定一棵二叉树，想象自己站在它的右侧，按照从顶部到底部的顺序，返回从右侧所能看到的节点值。
示例:
输入: [1,2,3,null,5,null,4]
输出: [1, 3, 4]
解释:
1 <---
/ \
2 3 <---
\ \
5 4 <---
方法一：层次遍历
将每层最后一个元素放到结果中
public List<Integer> rightSideView(TreeNode root) {
Queue<TreeNode> queue = new LinkedList<>();
List<Integer> ans = new ArrayList<>();
if (root == null) {
return ans;
}
queue.offer(root);
while(!queue.isEmpty()) {
int size = queue.size();
for (int i = 0; i < size; i++){
TreeNode node = queue.poll();
if (i == size - 1) {
ans.add(node.val);
}
if (node.left != null) {
queue.offer(node.left);
}
if (node.right != null) {
queue.offer(node.right);
}
}
}
return ans;
}
时间复杂度O(n)，n为结点个数
空间复杂度O(n)
方法二：深度优先
按照 根->右->左 的方式遍历，每层第一次访问到的元素就是最右边的元素（同理，先序访问的就是最左边的）
现在存在的问题是怎么确定一个元素是不是这层第一次被访问的元素：
先回溯过程中，给每层加个高度，将高度加到set中，如果set不存在这一层，说明是第一次访问
public List<Integer> rightSideView(TreeNode root) {
List<Integer> ans = new ArrayList<>();
if (root == null) {
return ans;
}
Set<Integer> set = new HashSet<>();//用于存放层数，好判断是否第一次遍历这一层
dfs(root,0,set,ans);
return ans;
}
public void dfs(TreeNode root, int level, Set<Integer> set, List<Integer> ans) {
if (!set.contains(level)) {
ans.add(root.val);
set.add(level);
}
if (root.right != null) {
dfs(root.right, level + 1, set, ans);
}
if (root.left != null) {
dfs(root.left, level + 1, set, ans);
}
}
时间复杂度O(n)，n为结点个数
空间复杂度O(n)
二叉树最大宽度
给定一个二叉树，编写一个函数来获取这个树的最大宽度。树的宽度是所有层中的最大宽度。这个二叉树与满二叉树（full binary tree）结构相同，但一些节点为空。
每一层的宽度被定义为两个端点（该层最左和最右的非空节点，两端点间的null节点也计入长度）之间的长度。
示例 1:
输入:
1
/ \
3 2
/ \ \
5 3 9
输出: 4
解释: 最大值出现在树的第 3 层，宽度为 4 (5,3,null,9)。
示例 2:
输入:
1
/
3
/ \
5 3
输出: 2
解释: 最大值出现在树的第 3 层，宽度为 2 (5,3)。
示例 3:
输入:
1
/ \
3 2
/
5
输出: 2
解释: 最大值出现在树的第 2 层，宽度为 2 (3,2)。
示例 4:
输入:
1
/ \
3 2
/ \
5 9
/ \
6 7
输出: 8
解释: 最大值出现在树的第 4 层，宽度为 8 (6,null,null,null,null,null,null,7)
方法一：层次遍历
记录每个结点在当层的位置，每层的宽度为这一层最后一个结点的位置减去第一个结点的位置再加1
class AnnotatedNode {
TreeNode node;
int pos;
public AnnotatedNode(TreeNode node, int pos) {
this.node = node;
this.pos = pos;
}
}
public int widthOfBinaryTree(TreeNode root) {
if (root == null) {
return 0;
}
Deque<AnnotatedNode> queue = new LinkedList<>();
int maxWidth = 0;
queue.offer(new AnnotatedNode(root, 0));
while (!queue.isEmpty()) {
int size = queue.size();
maxWidth = Math.max(maxWidth, queue.peekLast().pos - queue.peekFirst().pos + 1);
for (int i = 0; i < size; i++) {
AnnotatedNode node = queue.pollFirst();
if (node.node.left != null) {
queue.addLast(new AnnotatedNode(node.node.left, node.pos * 2));
}
if (node.node.right != null) {
queue.addLast(new AnnotatedNode(node.node.right, node.pos * 2 + 1));
}
}
}
return maxWidth;
}
方法二：深度优先遍历
先序遍历，记录每一层最左边节点的位置，每遍历到一个节点就更新能取到的最大宽度
private int res;
// k:depth v:最左边节点的位置
private Map<Integer, Integer> map = new HashMap<>();
public int widthOfBinaryTree(TreeNode root) {
dfs(root, 0, 0);
return res;
}
private void dfs(TreeNode root, int depth, int pos) {
if (root == null) {
return;
}
if (!map.containsKey(depth)) {
map.put(depth, pos);
}
res = Math.max(res, pos - map.get(depth) + 1);
dfs(root.left, depth + 1, pos * 2);
dfs(root.right, depth + 1, pos * 2 + 1);
}
完全二叉树的节点个数
给你一棵完全二叉树 的根节点 root ，求出该树的节点个数。
完全二叉树 的定义如下：在完全二叉树中，除了最底层节点可能没填满外，其余每层节点数都达到最大值，并且最下面一层的节点都集中在该层最左边的若干位置。若最底层为第 h 层，则该层包含 1~ 2h个节点。
示例 1：
输入：root = [1,2,3,4,5,6]
输出：6
方法一：二分查找+位运算
先确定层数，然后根据层数在可能的总数范围内二分查找
public int countNodes(TreeNode root) {
if (root == null) {
return 0;
}
TreeNode node = root;
// 层数
int level = 0;
while (node != null) {
level++;
node = node.left;
}
// 去掉最后一层
level = level - 1;
// low：最后一层就一个节点，high：最后一层全满 时的节点总数
int low = 1 << level, high = (1 << (level + 1)) - 1;
while (low < high) {
int mid = (low + high + 1) / 2;
if (exists(root, level, mid)) {
low = mid;
} else {
high = mid - 1;
}
}
return low;
}
private boolean exists(TreeNode root, int level, int k) {
int bits = 1 << (level - 1);
while (root != null && bits > 0) {
if ((bits & k) == 0) {
root = root.left;
} else {
root = root.right;
}
bits >>= 1;
}
return root != null;
}
时间复杂度：O(log2)2，其中 n 是完全二叉树的节点数。
首先需要 O(h)的时间得到完全二叉树的最大层数，其中 h 是完全二叉树的最大层数。
使用二分查找确定节点个数时，需要查找的次数为 O(log2h)=O(h)，每次查找需要遍历从根节点开始的一条长度为 h 的路径，需要 O(h) 的时间，因此二分查找的总时间复杂度是 O(h2)。
因此总时间复杂度是 O(h2)。由于完全二叉树满足2h≤n<2 h+1，因此有 O(h)=O(logn)， O(h2)=O(log2)2
方法二：比较左右子树的层数
对于普通的树：
public int countNodes(TreeNode root) {
if (root == null){
return 0;
}
return countNodes(root.left) + countNodes(root.right) + 1;
}
对于完全二叉树：
- 如果左右子树层数相同，说明左子树是满的，不完全出现的部分在右子树，可以先求得左子树的结点总数加上根结点，再递归计算右子树的结点数
- 如果左右子树层数不相同，说明右子树是满的，不完全出现的部分在左子树，可以先求得右子树的结点总数加上根结点，再递归计算左子树的结点数
public int countNodes(TreeNode root) {
if (root == null){
return 0;
}
int leftLevel = getLevel(root.left);
int rightLevel = getLevel(root.right);
if (leftLevel == rightLevel) {
return (1 << leftLevel ) + countNodes(root.right);
}
return (1 << rightLevel) + countNodes(root.left);
}
private int getLevel(TreeNode root) {
int level = 0;
while (root != null) {
level++;
root = root.left;
}
return level;
}
时间复杂度：O(n)=O(logn)2，T(n)=T(n/2)+logn
左叶子之和
给定二叉树的根节点 root ，返回所有左叶子之和。
示例 1：
输入: root = [3,9,20,null,null,15,7]
输出: 24
解释: 在这个二叉树中，有两个左叶子，分别是 9 和 15，所以返回 24
迭代
public int sumOfLeftLeaves(TreeNode root) {
if (root == null) {
return 0;
}
Queue<TreeNode> queue = new LinkedList<>();
queue.add(root);
int sum = 0;
while (!queue.isEmpty()) {
root = queue.poll();
if (root.left != null) {
queue.add(root.left);
if (root.left.left == null && root.left.right == null) {
sum += root.left.val;
}
}
if (root.right != null) {
queue.add(root.right);
}
}
return sum;
}
递归
int sum;
public int sumOfLeftLeaves(TreeNode root) {
dfs(root);
return sum;
}
private void dfs(TreeNode root) {
if (root == null) {
return;
}
if (root.left != null) {
if (root.left.left == null && root.left.right == null) {
sum += root.left.val;
}
}
dfs(root.left);
dfs(root.right);
}
找树左下角的值
给定一个二叉树的 根节点 root，请找出该二叉树的 **最底层 最左边 **节点的值。
假设二叉树中至少有一个节点。
示例 1:
输入: [1,2,3,4,null,5,6,null,null,7]
输出: 7
迭代
public int findBottomLeftValue(TreeNode root) {
if (root == null) {
return 0;
}
Queue<TreeNode> queue = new LinkedList<>();
queue.add(root);
int res = 0;
while (!queue.isEmpty()) {
int size = queue.size();
res = queue.peek().val;
for (int i = 0; i < size; i++) {
root = queue.poll();
if (root.left != null) {
queue.add(root.left);
}
if (root.right != null) {
queue.add(root.right);
}
}
}
return res;
}
递归
private int res = 0;
private int maxLevel = -1;
public int findBottomLeftValue(TreeNode root) {
dfs(root, 0);
return res;
}
private void dfs(TreeNode root, int level) {
if (root == null) {
return;
}
if (level > maxLevel) {
maxLevel = level;
res = root.val;
}
dfs(root.left, level + 1);
dfs(root.right, level + 1);
}
最大二叉树
给定一个不重复的整数数组 nums 。 最大二叉树 可以用下面的算法从 nums 递归地构建:
- 创建一个根节点，其值为
nums中的最大值。 - 递归地在最大值 左边 的 子数组前缀上 构建左子树。
- 递归地在最大值 右边 的 子数组后缀上 构建右子树。
返回nums构建的 ****最大二叉树 **。
示例 1：
输入：nums = [3,2,1,6,0,5]
输出：[6,3,5,null,2,0,null,null,1]
解释：递归调用如下所示：
[3,2,1,6,0,5] 中的最大值是 6 ，左边部分是 [3,2,1] ，右边部分是 [0,5] 。
[3,2,1] 中的最大值是 3 ，左边部分是 [] ，右边部分是 [2,1] 。
空数组，无子节点。
[2,1] 中的最大值是 2 ，左边部分是 [] ，右边部分是 [1] 。
空数组，无子节点。
只有一个元素，所以子节点是一个值为 1 的节点。
[0,5] 中的最大值是 5 ，左边部分是 [0] ，右边部分是 [] 。
只有一个元素，所以子节点是一个值为 0 的节点。
空数组，无子节点。
方法一：暴力
每次找到最大值，然后将数组分为两半
public TreeNode constructMaximumBinaryTree(int[] nums) {
return dfs(nums, 0, nums.length - 1);
}
private TreeNode dfs(int[] nums, int left, int right) {
if (left > right) {
return null;
}
int index = maxIndex(nums, left, right);
TreeNode root = new TreeNode(nums[index]);
root.left = dfs(nums, left, index - 1);
root.right = dfs(nums, index + 1, right);
return root;
}
private int maxIndex(int[] nums, int left, int right) {
int index = left;
while (left <= right) {
if (nums[index] < nums[left]) {
index = left;
}
left++;
}
return index;
}
时间复杂度：O(n2)
方法二：单调栈
维护一个递减的栈
以测试案例为例，一个输入序列：[3, 2, 1, 6, 0, 5]。 设置一个辅助栈，从大到小存储。 过程如下：
- 首先入栈3
- 2 比 3 小，入栈
- 1 比 2 小，入栈
- 6 大于1，因此要弹出1，1在2和6之间选择二者之间较小的元素作为父节点，因此选择2。1在2的右侧，使得1作为2的右子节点
- 弹出1后，6仍然比2大，同理2要在3和6之间选择一个作为父节点。3比6小，因此选择3。2在3的右侧，因此2作为3的右子节点
- 同理弹出3，让3作为6的左子节点
- 入栈6
- 入栈0
- 入栈5的时候比0大，要弹出0，选择5作为父节点，并且0是5的左孩子
- 弹出5，左侧是6，作为5的父节点
- 6最后弹出，就是根节点
public TreeNode constructMaximumBinaryTree(int[] nums) {
Stack<TreeNode> stack = new Stack<>();
for (int num : nums) {
TreeNode cur = new TreeNode(num);
while (!stack.isEmpty() && stack.peek().val < num) {
TreeNode top = stack.pop();
if (!stack.isEmpty() && stack.peek().val < num) {
// 栈中还有满足条件的元素，即还有递减序列，nums后一个为前一个的右子树
stack.peek().right = top;
} else {
// 说明栈顶为空或比当前小，将其作为当前位置的左子树
cur.left = top;
}
}
stack.add(cur);
}
TreeNode root = null;
while (!stack.isEmpty()) {
TreeNode top = stack.pop();
if (!stack.isEmpty()) {
stack.peek().right = top;
}
root = top;
}
return root;
}
时间复杂度：O(n)
