LeetCode 树的定义
二叉树
public class TreeNode { int val; TreeNode left; TreeNode right; TreeNode(int x) { val = x; } }
N叉树
public class Node { public int val; public List<Node> children; public Node() { } public Node(int _val, List<Node> _children) { val = _val; children = _children; } }
二叉树遍历
二叉树最基本的遍历方式就是：前序遍历、中序遍历和后序遍历。
- 前序遍历首先访问根节点，然后遍历左子树，最后遍历右子树。
- 中序遍历是先遍历左子树，然后访问根节点，然后遍历右子树。
- 后序遍历是先遍历左子树，然后遍历右子树，最后访问树的根节点。
简单概况如下：
- 前序遍历：根左右
- 中序遍历：左根右
- 后序遍历：左右根
TIPS：前中后序遍历区别在于三字中的中间那个字，前、中、后序分别对应左、根、右。
二叉树前序遍历
- 二叉树的前序遍历
给定一个二叉树，返回它的 前序 遍历。
示例:
输入: [1,null,2,3] 1 \ 2 / 3 输出: [1,2,3] `进阶`: 递归算法很简单，你可以通过迭代算法完成吗？
递归
public List<Integer> preorderTraversal(TreeNode root) { List<Integer> ans = new ArrayList<>(); robot(root, ans); return ans; } private void robot(TreeNode p, List<Integer> ans) { if(p == null) return; // 根左右 ans.add(p.val); robot(p.left, ans); robot(p.right, ans); }
迭代
迭代步骤：
- 从根节点开始，每次迭代弹出当前栈顶元素
- 将其孩子节点压入栈中（先压右孩子再压左孩子）
public List<Integer> preorderTraversal2(TreeNode root) { List<Integer> ans = new ArrayList<>(); Stack<TreeNode> stack = new Stack<>(); // 将根节点入栈 stack.push(root); while (!stack.isEmpty()) { // 取出栈顶元素 TreeNode tmp = stack.pop(); if (tmp != null) { ans.add(tmp.val); // 将其孩子节点压入栈中（先右节点、再左节点） stack.add(tmp.right); stack.add(tmp.left); } } return ans; }
算法复杂度:
- 时间复杂度：树中每个节点都遍历一次，因此时间复杂度为 O(N)，其中 N 为树中节点的数量。
- 空间复杂度：
- 最坏情况：树为链表，树的高度=树的节点个数，此时空间复杂度是 O(N)。
- 最好情况：树高度平衡，此时空间复杂度是 O(logn)。
二叉树中序遍历
- 二叉树的中序遍历
给定一个二叉树，返回它的 中序 遍历。
示例:
输入: [1,null,2,3] 1 \ 2 / 3 输出: [1,3,2]
进阶: 递归算法很简单，你可以通过迭代算法完成吗？
递归
public List<Integer> inorderTraversal(TreeNode root) { List<Integer> ans = new ArrayList<>(); robot(root, ans); return ans; } private void robot(TreeNode root, List<Integer> ans) { if (root == null) { return; } // 左根右 robot(root.left, ans); ans.add(root.val); robot(root.right, ans); }
迭代
public List<Integer> inorderTraversal(TreeNode root) { List<Integer> ans = new ArrayList<>(); Stack<TreeNode> stack = new Stack<>(); while (!stack.isEmpty() || root != null) { // 一直放入左儿子（左） while (root != null) { stack.push(root); root = root.left; } // 访问当前元素（根），把右儿子入栈（右） if (!stack.isEmpty()) { root = stack.pop(); ans.add(root.val); root = root.right; } } return ans; }
算法复杂度
- 时间复杂度：O(n)。递归函数 T(n) = 2⋅T(n/2)+1。
- 空间复杂度：最坏情况下需要空间O(n)，平均情况为O(logn)。
二叉树后序遍历
- 二叉树的后序遍历
给定一个二叉树，返回它的 后序 遍历。
示例:
输入: [1,null,2,3] 1 \ 2 / 3 输出: [3,2,1]
进阶: 递归算法很简单，你可以通过迭代算法完成吗？
递归
public List<Integer> postorderTraversal(TreeNode root) { List<Integer> ans = new ArrayList<>(); robot(root, ans); return ans; } private void robot(TreeNode p, List<Integer> ans) { if (p == null) { return; } // 左右根 robot(p.left, ans); robot(p.right, ans); ans.add(p.val); }
后序遍历的非递归写法有些麻烦，因为节点第一次访问时并不打印，而是在第二次遍历时才打印。所以需要一个变量来标记该结点是否访问过。
迭代：利用辅助类
public class StackNode { TreeNode root; boolean visit; StackNode(TreeNode root) { this.root = root; } } public List<Integer> postorderTraversal2(TreeNode root) { List<Integer> ans = new ArrayList<>(); if (root == null) { return ans; } Stack<StackNode> stack = new Stack<>(); StackNode node; stack.push(new StackNode(root)); while (!stack.isEmpty()) { node = stack.pop(); if (node == null) { continue; } if (!node.visit) { node.visit = true; stack.push(node); if (node.root.right != null) { stack.push(new StackNode(node.root.right)); } if (node.root.left != null) { stack.push(new StackNode(node.root.left)); } } else if (node.root != null) { ans.add(node.root.val); } } return ans; }
迭代：逆序输出
public List<Integer> postorderTraversal3(TreeNode root) { LinkedList<Integer> ans = new LinkedList<>(); if (root == null) { return ans; } Stack<TreeNode> stack = new Stack<>(); stack.push(root); while (!stack.isEmpty()) { TreeNode node = stack.pop(); ans.addFirst(node.val); if (node.left != null) { stack.push(node.left); } if (node.right != null) { stack.push(node.right); } } return ans; }
算法复杂度：
- 时间复杂度：访问每个节点恰好一次，因此时间复杂度为 O(N)，其中 N 是节点的个数，也就是树的大小。
- 空间复杂度：取决于树的结构，最坏情况需要保存整棵树，因此空间复杂度为 O(N)。
二叉树的层次遍历
- 二叉树的层次遍历
给定一个二叉树，返回其按层次遍历的节点值。 （即逐层地，从左到右访问所有节点）。
例如：给定二叉树: [3,9,20,null,null,15,7],
3 / \ 9 20 / \ 15 7
返回其层次遍历结果：
[ [3], [9,20], [15,7] ]
递归
首先确认树非空，然后调用递归函数 helper(node, level)，参数是当前节点和节点的层次。
算法过程:
- ans 为结果列表，level 为当前遍历的层数（初始为0）
- 若 ans 的长度 = level，向 ans 增加一个空列表
- 将节点值放入 ans 的第 level 个列表结尾
- 遍历左右子节点，此时 level + 1
public List<List<Integer>> levelOrder(TreeNode root) { List<List<Integer>> ans = new ArrayList<>(); robot(root, ans, 0); return ans; } private void robot(TreeNode root, List<List<Integer>> ans, int level) { if (root == null) { return; } if (ans.size() == level) { ans.add(new ArrayList()); } ans.get(level).add(root.val); robot(root.left, ans, level + 1); robot(root.right, ans, level + 1); }
复杂度分析
- 时间复杂度：O(N)，因为每个节点恰好会被运算一次。
- 空间复杂度：O(N)，保存输出结果的数组包含 N 个节点的值。
迭代
算法过程：
第 0 层只包含根节点 root ，算法实现如下：
- 初始化队列只包含一个节点 root 和层次编号 0 ： level = 0。
- 当队列非空的时候：
- 新建一个空列表，表示当前层结果 current。
- 计算当前层有多少个元素：等于队列的长度。
- 将这些元素从队列中弹出，并加入 current 列表中。
- 将他们的孩子节点作为下一层压入队列中。
- 将 当前层结果 current 放入 ans 中。
- 进入下一层循环。
public List<List<Integer>> levelOrder(TreeNode root) { List<List<Integer>> ans = new ArrayList<>(); if (root == null) { return ans; } Queue<TreeNode> queue = new LinkedList<>(); queue.add(root); while (!queue.isEmpty()) { List<Integer> current = new ArrayList<>(); // 当前层的元素个数 int length = queue.size(); for (int i = 0; i < length; ++i) { TreeNode node = queue.remove(); // 放入结果 current.add(node.val); // 依次将 node 的左右子节点加入队列 if (node.left != null) { queue.add(node.left); } if (node.right != null) { queue.add(node.right); } } ans.add(current); } return ans; }
复杂度分析
- 时间复杂度：O(N)，因为每个节点恰好会被运算一次。
- 空间复杂度：O(N)，保存输出结果的数组包含 N 个节点的值。
二叉树的右视图
- 二叉树的右视图
给定一棵二叉树，想象自己站在它的右侧，按照从顶部到底部的顺序，返回从右侧所能看到的节点值。
示例:
输入: [1,2,3,null,5,null,4] 输出: [1, 3, 4] 解释: 1 <--- / \ 2 3 <--- \ \ 5 4 <---
本题是层序遍历的变种，层序遍历是存储二叉树每行的每个元素，而本题仅存储二叉树每行的最后一个元素。
递归
public List<Integer> rightSideView(TreeNode root) { List<Integer> ans = new ArrayList<>(); robot(root, ans, 0); return ans; } private void robot(TreeNode root, List<Integer> ans, int level) { if (root == null) { return; } if (ans.size() == level) { ans.add(root.val); } // 层序遍历的 ans 是一个 List<List<Integer>，是 ans.get(level).add(root.val); ans.set(level, root.val); robot(root.left, ans, level + 1); robot(root.right, ans, level + 1); }
迭代
public List<Integer> rightSideView(TreeNode root) { List<Integer> ans = new ArrayList<>(); if (root == null) { return ans; } Queue<TreeNode> queue = new LinkedList<>(); queue.add(root); while (!queue.isEmpty()) { int current = 0; // 当前层的元素个数 int length = queue.size(); for (int i = 0; i < length; ++i) { TreeNode node = queue.remove(); // 放入结果 current = node.val; // 依次将 node 的左右子节点加入队列 if (node.left != null) { queue.add(node.left); } if (node.right != null) { queue.add(node.right); } } ans.add(current); } return ans; }
在每个树行中找最大值
- 在每个树行中找最大值
您需要在二叉树的每一行中找到最大的值。
示例：
输入:
1 / \ 3 2 / \ \ 5 3 9 输出: [1, 3, 9]
本题也是层序遍历的变种，层序遍历是存储二叉树每行的每个元素，而本题仅存储二叉树每行的最大元素。
递归
public List<Integer> largestValues(TreeNode root) { List<Integer> ans = new ArrayList<>(); robot(root, ans, 0); return ans; } private void robot(TreeNode root, List<Integer> ans, int level) { if (root == null) { return; } if (ans.size() <= level) { ans.add(Integer.MIN_VALUE); } ans.set(level, Math.max(ans.get(level), root.val)); robot(root.left, ans, level + 1); robot(root.right, ans, level + 1); }
迭代
public List<Integer> largestValues(TreeNode root) { List<Integer> ans = new ArrayList<>(); if (root == null) { return ans; } Queue<TreeNode> queue = new LinkedList<>(); queue.add(root); while (!queue.isEmpty()) { int current = Integer.MIN_VALUE; // 当前层的元素个数 int length = queue.size(); for (int i = 0; i < length; ++i) { TreeNode node = queue.remove(); // 放入结果（变化的地方） current = Math.max(current, node.val); // 依次将 node 的左右子节点加入队列 if (node.left != null) { queue.add(node.left); } if (node.right != null) { queue.add(node.right); } } ans.add(current); } return ans; }
二叉树的垂序遍历
- 二叉树的垂序遍历
给定二叉树，按垂序遍历返回其结点值。
对位于 (X, Y) 的每个结点而言，其左右子结点分别位于 (X-1, Y-1) 和 (X+1, Y-1)。
把一条垂线从 X = -infinity 移动到 X = +infinity ，每当该垂线与结点接触时，我们按从上到下的顺序报告结点的值（ Y 坐标递减）。
如果两个结点位置相同，则首先报告的结点值较小。
按 X 坐标顺序返回非空报告的列表。每个报告都有一个结点值列表。
示例 1：
输入：[3,9,20,null,null,15,7] 输出：[[9],[3,15],[20],[7]] 解释： 在不丧失其普遍性的情况下，我们可以假设根结点位于 (0, 0)： 然后，值为 9 的结点出现在 (-1, -1)； 值为 3 和 15 的两个结点分别出现在 (0, 0) 和 (0, -2)； 值为 20 的结点出现在 (1, -1)； 值为 7 的结点出现在 (2, -2)。
示例 2：
输入：[1,2,3,4,5,6,7] 输出：[[4],[2],[1,5,6],[3],[7]] 解释： 根据给定的方案，值为 5 和 6 的两个结点出现在同一位置。 然而，在报告 "[1,5,6]" 中，结点值 5 排在前面，因为 5 小于 6。
提示：
树的结点数介于 1 和 1000 之间。
每个结点值介于 0 和 1000 之间。
解题思路
设根节点的(x,y)=(0,0)，对于节点坐标(x,y)，其左节点坐标为(x-1,y-1)，右节点坐标为(x+1,y-1)。
- 构造 List posNodes，遍历二叉树每个节点，填入 PositionNode 的 x 坐标、y 坐标、val 值。
- 将 posNodes 展开成 key 是 x 坐标、value 是对应 PositionNode 的 positionMap，注意这里使用 TreeMap，因为要对 x 坐标排序。
- 构建结果 ans：遍历 positionMap，相同位置节点，按照自然顺序排序（即先按照 Y 降序排列；若 Y 相同，则按照 val 升序排列）
代码
public class PositionNode { int val; int x; int y; PositionNode(int val, int x, int y) { this.val = val; this.x = x; this.y = y; } public int getVal() { return val; } public int getX() { return x; } public int getY() { return y; } } public List<List<Integer>> verticalTraversal(TreeNode root) { // 构建节点的位置信息 List<PositionNode> posNodes = new ArrayList<>(); robot(root, posNodes, 0, 0); // 将 posNodes 展开成 key 是 x 坐标、value 是对应 PositionNode 的 map // 注意这里使用 TreeMap，因为要对 x 坐标排序 Map<Integer, List<PositionNode>> positionMap = posNodes.stream().collect( Collectors.groupingBy(PositionNode::getX, TreeMap::new, Collectors.toList())); // 构建结果 List<List<Integer>> ans = new ArrayList<>(); positionMap.forEach((k, v) -> { // 题目要求：相同位置节点，按照自然顺序排序（即先按照 Y 降序排列；若 Y 相同，则按照 val 升序排列） v.sort(Comparator.comparing(PositionNode::getY).reversed() .thenComparing(PositionNode::getVal)); ans.add(v.stream().map(PositionNode::getVal).collect(Collectors.toList())); }); return ans; } private void robot(TreeNode root, List<PositionNode> posNodes, int x, int y) { if (root == null) { return; } posNodes.add(new PositionNode(root.val, x, y)); // 根节点的(x,y)=(0,0)，若某个节点坐标为(x,y)，则左节点坐标为(x-1,y-1)，右节点坐标为(x+1,y-1) robot(root.left, posNodes, x - 1, y - 1); robot(root.right, posNodes, x + 1, y - 1);
二叉树的锯齿形层次遍历
- 二叉树的锯齿形层次遍历
给定一个二叉树，返回其节点值的锯齿形层次遍历。（即先从左往右，再从右往左进行下一层遍历，以此类推，层与层之间交替进行）。
例如：
给定二叉树 [3,9,20,null,null,15,7],
3 / \ 9 20 / \ 15 7
返回锯齿形层次遍历如下：
[ [3], [20,9], [15,7] ]
本题是层序遍历的变种，仅需将层序遍历的偶数行逆序即可。
递归
public List<List<Integer>> zigzagLevelOrder(TreeNode root) { List<List<Integer>> ans = new ArrayList<>(); robot(root, ans, 0); // 与层序遍历相比，变化的部分 for (int i = 1; i < ans.size(); i += 2) { Collections.reverse(ans.get(i)); } return ans; } private void robot(TreeNode root, List<List<Integer>> ans, int level) { if (root == null) { return; } if (ans.size() == level) { ans.add(new ArrayList()); } ans.get(level).add(root.val); robot(root.left, ans, level + 1); robot(root.right, ans, level + 1); }
迭代
public List<List<Integer>> zigzagLevelOrder(TreeNode root) { List<List<Integer>> ans = new ArrayList<>(); if (root == null) { return ans; } Queue<TreeNode> queue = new LinkedList<>(); queue.add(root); while (!queue.isEmpty()) { List<Integer> current = new ArrayList<>(); // 当前层的元素个数 int length = queue.size(); for (int i = 0; i < length; ++i) { TreeNode node = queue.remove(); // 放入结果 current.add(node.val); // 依次将 node 的左右子节点加入队列 if (node.left != null) { queue.add(node.left); } if (node.right != null) { queue.add(node.right); } } ans.add(current); } // 与层序遍历相比，变化的部分 for (int i = 1; i < ans.size(); i += 2) { Collections.reverse(ans.get(i)); } return ans; }
N 叉树遍历
N叉树的层序遍历
- N叉树的层序遍历
给定一个 N 叉树，返回其节点值的层序遍历。 (即从左到右，逐层遍历)。
例如，给定一个 3叉树 :
返回其层序遍历:
[ [1], [3,2,4], [5,6] ]
说明:
- 树的深度不会超过 1000。
- 树的节点总数不会超过 5000。
public List<List<Integer>> levelOrder(Node root) { List<List<Integer>> ans = new ArrayList<>(); robot(root, ans, 0); return ans; } private void robot(Node root, List<List<Integer>> ans, int level) { if (root == null) { return; } if (ans.size() <= level) { ans.add(new ArrayList<>()); } ans.get(level).add(root.val); if (root.children == null) { return; } for (Node child : root.children) { robot(child, ans, level + 1); } }
N叉树的前序遍历
- N叉树的前序遍历
给定一个 N 叉树，返回其节点值的前序遍历。
例如，给定一个 3叉树 :
返回其前序遍历: [1,3,5,6,2,4]。
说明: 递归法很简单，你可以使用迭代法完成此题吗？
递归
public List<Integer> preorder(Node root) { List<Integer> ans = new ArrayList<>(); robot(root, ans); return ans; } private void robot(Node root, List<Integer> ans) { if (root == null) { return; } ans.add(root.val); if (root.children == null) { return; } for (Node child : root.children) { robot(child, ans); } }
迭代
public List<Integer> preorder(Node root) { List<Integer> ans = new ArrayList<>(); if (root == null) { return ans; } Deque<Node> deque = new ArrayDeque<>(); deque.push(root); while (!deque.isEmpty()) { Node tmp = deque.pop(); if (tmp != null) { ans.add(tmp.val); if (tmp.children == null) { continue; } for (int i = tmp.children.size() - 1; i >= 0; i--) { deque.push(tmp.children.get(i)); } } } return ans; }
N叉树的后序遍历
- N叉树的后序遍历
给定一个 N 叉树，返回其节点值的后序遍历。
例如，给定一个 3叉树 :
返回其后序遍历: [5,6,3,2,4,1].
说明: 递归法很简单，你可以使用迭代法完成此题吗?
递归
public List<Integer> postorder(Node root) { List<Integer> ans = new ArrayList<>(); robot(root, ans); return ans; } private void robot(Node root, List<Integer> ans) { if (root == null) { return; } if (root.children != null) { for (Node child : root.children) { robot(child, ans); } } ans.add(root.val); }
迭代
// 后续遍历：左右中 // 迭代顺序：中右左 public List<Integer> postorder(Node root) { List<Integer> ans = new ArrayList<>(); if (root == null) { return ans; } Stack<Node> stack = new Stack<>(); stack.push(root); while (!stack.isEmpty()) { Node pop = stack.pop(); ans.add(pop.val); List<Node> children = pop.children; if (children == null) { continue; } for (Node child : children) { stack.push(child); } } Collections.reverse(ans); return ans; }
二叉搜索树
不同的二叉搜索树
- 不同的二叉搜索树
给定一个整数 n，求以 1 … n 为节点组成的二叉搜索树有多少种？
示例:
输入: 3 输出: 5 解释: 给定 n = 3, 一共有 5 种不同结构的二叉搜索树: 1 3 3 2 1 \ / / / \ \ 3 2 1 1 3 2 / / \ \ 2 1 2 3
public int numTrees(int n) { int[] ans = new int[n + 2]; ans[0] = 1; ans[1] = 1; ans[2] = 2; // f(n) = f(0)*f(n-1) + f(1)*f(n-2) + …… for(int i = 3; i <= n; i++) { for(int j = 0; j <= i - 1; j++) { ans[i] += ans[j] * ans[i - j - 1]; } } return ans[n]; }
不同的二叉搜索树 II
- 不同的二叉搜索树 II
给定一个整数 n，生成所有由 1 … n 为节点所组成的二叉搜索树。
示例:
输入: 3 输出: [ [1,null,3,2], [3,2,null,1], [3,1,null,null,2], [2,1,3], [1,null,2,null,3] ] 解释: 以上的输出对应以下 5 种不同结构的二叉搜索树： 1 3 3 2 1 \ / / / \ \ 3 2 1 1 3 2 / / \ \ 2 1 2 3
public List<TreeNode> generateTrees(int n) { if(n <= 0) return new ArrayList<>(); return build(1, n); } private List<TreeNode> build(int start, int end) { List<TreeNode> roots = new ArrayList<>(); if(start > end) { // null也要放入，否则下面的双重循环进不去 roots.add(null); return roots; } if(start == end) { roots.add(new TreeNode(start)); return roots; } for(int i = start; i <= end; i++) { List<TreeNode> leftList = build(start, i - 1); List<TreeNode> rightList = build(i + 1, end); for(TreeNode left : leftList) { for(TreeNode right : rightList) { TreeNode root = new TreeNode(i); root.left = left; root.right = right; roots.add(root); } } } return roots; }
验证二叉搜索树
- 验证二叉搜索树
给定一个二叉树，判断其是否是一个有效的二叉搜索树。
假设一个二叉搜索树具有如下特征：
- 节点的左子树只包含
小于当前节点的数。 - 节点的右子树只包含
大于当前节点的数。 - 所有左子树和右子树自身必须也是二叉搜索树。
示例 1:
输入: 2 / \ 1 3 输出: true
示例 2:
输入: 5 / \ 1 4 / \ 3 6 输出: false 解释: 输入为: [5,1,4,null,null,3,6]。 根节点的值为 5 ，但是其右子节点值为 4 。
public boolean isValidBST(TreeNode root) { // 用long型 return isValidBST(root, Long.MIN_VALUE, Long.MAX_VALUE); } private boolean isValidBST(TreeNode root, long min, long max) { if (root == null) { return true; } if (root.val >= max || root.val <= min) { return false; } return isValidBST(root.left, min, root.val) && isValidBST(root.right, root.val, max); }
恢复二叉搜索树
- 恢复二叉搜索树
二叉搜索树中的两个节点被错误地交换。
请在不改变其结构的情况下，恢复这棵树。
示例 1:
输入: [1,3,null,null,2] 1 / 3 \ 2 输出: [3,1,null,null,2] 3 / 1 \ 2
示例 2:
输入: [3,1,4,null,null,2] 3 / \ 1 4 / 2 输出: [2,1,4,null,null,3] 2 / \ 1 4 / 3
进阶:
- 使用 O(n) 空间复杂度的解法很容易实现。
- 你能想出一个只使用常数空间的解决方案吗？
TreeNode first = null, second = null; TreeNode pre = new TreeNode(Integer.MIN_VALUE); public void recoverTree(TreeNode root) { if(root == null) return; robot(root); if(first != null && second != null) { int tmp = first.val; first.val = second.val; second.val = tmp; } } private void robot(TreeNode root) { if(root == null) return; robot(root.left); // 找到交换的两个节点 if(first == null && pre.val > root.val) { first = pre; } if(first != null && pre.val > root.val) { second = root; } pre = root; robot(root.right); }
常见的二叉树系统题解（二）：https://developer.aliyun.com/article/1416668
