- LeetCode
- 105. 从前序与中序遍历序列构造二叉树">105. 从前序与中序遍历序列构造二叉树
- 112. 路径总和">112. 路径总和
- 113. 路径总和 II">113. 路径总和 II
- 437. 路径总和 III">437. 路径总和 III
- 129. 求根到叶子结点数字之和">129. 求根到叶子结点数字之和
- 257. 二叉树的所有路径">257. 二叉树的所有路径
- 199. 二叉树的右视图">199. 二叉树的右视图
- 94. 二叉树的中序遍历">94. 二叉树的中序遍历
- 练习：
- 144. 二叉树的前序遍历">144. 二叉树的前序遍历
- 145. 二叉树的后序遍历">145. 二叉树的后序遍历
- 236. 二叉树的最近公共祖先">236. 二叉树的最近公共祖先
- 958. 二叉树的完全性检验">958. 二叉树的完全性检验
- 剑指 Offer
LeetCode
105. 从前序与中序遍历序列构造二叉树
112. 路径总和
给定一个二叉树和一个目标和，判断该树中是否存在根结点到叶子结点的路径，这条路径上所有结点值相加等于目标和。
class Solution {public boolean hasPathSum(TreeNode root, int sum) {if (root == null) return false;if (root.left == null && root.right == null) {return sum - root.val == 0;}return hasPathSum(root.left, sum-root.val) || hasPathSum(root.right, sum-root.val);}}
class Solution {public boolean hasPathSum(TreeNode root, int sum) {if (root == null) return false;Stack<TreeNode> st = new Stack<>();st.push(root);while (!st.empty()) {TreeNode t = st.pop();if (t.left == null && t.right == null) {if (t.val == sum) return true;}if (t.right != null) {t.right.val += t.val;st.push(t.right);}if (t.left != null) {t.left.val += t.val;st.push(t.left);}}return false;}}
113. 路径总和 II
给定一个二叉树和一个目标和，找到所有从根结点到叶子结点路径总和等于给定目标和的路径。**
class Solution {public List<List<Integer>> pathSum(TreeNode root, int sum) {List<List<Integer>> res = new ArrayList<>();if (root == null) return res;helper(new ArrayList<>(), res, root, sum);return res;}private void helper(List<Integer> list, List<List<Integer>> res, TreeNode root, int sum) {list.add(root.val);if (root.left == null && root.right == null) {int cur = 0;for (int n : list) {cur += n;}if (cur == sum) {res.add(new ArrayList<>(list));return;}}if (root.left != null) {helper(list, res, root.left, sum);list.remove(list.size() - 1);}if (root.right != null) {helper(list, res, root.right, sum);list.remove(list.size() - 1);}}}
437. 路径总和 III
给定一个二叉树，它的每个结点都存放着一个整数值。
找出路径和等于给定数值的路径总数。
路径不需要从根节点开始，也不需要在叶子节点结束，但是路径方向必须是向下的（只能从父节点到子节点）。
思路：
递归关系，是包含 root 结点和不包含 root 结点两种情况之和。
class Solution {public int pathSum(TreeNode root, int sum) {if (root == null) {return 0;}return dfs(root, sum) + pathSum(root.left, sum) + pathSum(root.right, sum);}private int dfs(TreeNode root, int sum) {int res = 0;if (root == null) {return 0;}if (root.val == sum) {res++;}res += dfs(root.left, sum - root.val);res += dfs(root.right, sum - root.val);return res;}}
129. 求根到叶子结点数字之和
给定一个二叉树，它的每个结点都存放一个 0-9 的数字，每条从根到叶子结点的路径都代表一个数字。
例如，从根到叶子结点路径 1->2->3 代表数字 123。
计算从根到叶子结点生成的所有数字之和。
思路：
常规解法，使用回溯法获取每一个 path，累加path的和。这样速度会比较慢。
更好的方法是，还是利用回溯的思想，不过我们将当前遍历到的结点值存到 cur 中。这样在遍历到下一个结点之前，我们已经有了累加值。
class Solution {private int res = 0;public int sumNumbers(TreeNode root) {if (root == null) return 0;helper(root, 0);return res;}private void helper(TreeNode root, int cur) {cur = root.val + cur*10;if (root.left == null && root.right == null) {res += cur;return;}if (root.left != null) helper(root.left, cur);if (root.right != null) helper(root.right, cur);return;}}
257. 二叉树的所有路径
给定一个二叉树，返回所有从根结点到叶子结点的路径。
思路：
回溯法，注意递归和非递归两种写法。递归关系：左节点和右节点的所有路径可以构成根节点的路径。
class Solution {
public List<String> binaryTreePaths(TreeNode root) {
List<String> paths = new ArrayList<>();
btPaths(root, paths, "");
return paths;
}
public void btPaths(TreeNode root, List<String> paths, String s) {
if(root == null) return;
s = s + root.val;
if(root.left == null && root.right == null) {
paths.add(s);
}
s = s + "->";
btPaths(root.left, paths, s);
btPaths(root.right, paths, s);
}
}
class Solution {
public List<String> binaryTreePaths(TreeNode root) {
List<String> list = new LinkedList<>();
if(root == null) return list;
Stack<TreeNode> stack = new Stack<>();
HashMap<TreeNode, String> map = new HashMap<>();
stack.push(root);
map.put(root, "" + root.val);
while(!stack.isEmpty()) {
TreeNode cur = stack.pop();
if(cur.left == null && cur.right == null) {
list.add(map.get(cur));
}
if (cur.right != null) {
stack.add(cur.right);
map.put(cur.right, map.get(cur) + "->" + cur.right.val);
}
if (cur.left != null) {
stack.add(cur.left);
map.put(cur.left, map.get(cur) + "->" + cur.left.val);
}
}
return list;
}
}
199. 二叉树的右视图
给定一棵二叉树，想象自己站在它的右侧，按照从顶部到底部的顺序，返回从右侧所能看到的节点值。
思路：
使用深度优先遍历完成，注意顺序。使用层序遍历（todo）。
class Solution {
public List<Integer> rightSideView(TreeNode root) {
List<List<Integer>> list = new ArrayList<>();
List<Integer> res = new ArrayList<>();
if(root == null) return res;
dfs(list, root, 0);
for (List<Integer> l : list) {
res.add(l.get(l.size()-1));
}
return res;
}
public void dfs(List<List<Integer>> res, TreeNode node, int level) {
if(node == null) return;
List<Integer> cur;
if(level >= res.size()) {
cur = new ArrayList<>();
cur.add(node.val);
res.add(cur);
} else {
cur = res.get(level);
cur.add(node.val);
}
dfs(res, node.left, level+1);
dfs(res, node.right, level+1);
}
}
94. 二叉树的中序遍历
给定一个二叉树，返回它的 中序 遍历。
思路：
注意递归和非递归的写法。
class Solution {
public List<Integer> inorderTraversal(TreeNode root) {
List<Integer> res = new ArrayList<>();
if (root == null) return res;
dfs(root, res);
return res;
}
private void dfs(TreeNode root, List<Integer> res) {
if (root.left != null) {
dfs(root.left, res);
}
res.add(root.val);
if (root.right != null) {
dfs(root.right, res);
}
}
}
class Solution {
public List<Integer> inorderTraversal(TreeNode root) {
List<Integer> res = new ArrayList<>();
Stack<TreeNode> stack = new Stack<>();
TreeNode cur = root;
while (cur != null || !stack.isEmpty()) {
while (cur != null) {
stack.push(cur);
cur = cur.left;
}
cur = stack.pop();
res.add(cur.val);
cur = cur.right;
}
return res;
}
}
练习：
144. 二叉树的前序遍历
145. 二叉树的后序遍历
236. 二叉树的最近公共祖先
958. 二叉树的完全性检验
剑指 Offer
剑指 Offer 32 - I. 从上到下打印二叉树
从上到下打印出二叉树的每个节点，同一层的节点按照从左到右的顺序打印。
思路：
广度优先搜索。
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
public int[] levelOrder(TreeNode root) {
List<Integer> list = new ArrayList<>();
Queue<TreeNode> queue = new LinkedList<>();
if (root == null) {
return new int[]{};
}
queue.offer(root);
while (!queue.isEmpty()) {
TreeNode node = queue.poll();
if (node.left != null) {
queue.offer(node.left);
}
if (node.right != null) {
queue.offer(node.right);
}
list.add(node.val);
}
int[] res = new int[list.size()];
for (int i = 0; i < list.size(); i++) {
res[i] = list.get(i);
}
return res;
}
}
剑指 Offer 32 - II. 从上到下打印二叉树 II
从上到下按层打印二叉树，同一层的节点按从左到右的顺序打印，每一层打印到一行。
思路：
广度优先搜索。
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
public List<List<Integer>> levelOrder(TreeNode root) {
List<List<Integer>> res = new ArrayList<>();
if (root == null) {
return res;
}
Queue<TreeNode> queue = new LinkedList<>();
queue.offer(root);
while (!queue.isEmpty()) {
int size = queue.size();
List<Integer> temp = new ArrayList<>();
for (int i = 0; i < size; i++) {
TreeNode node = queue.poll();
if (node.left != null) {
queue.offer(node.left);
}
if (node.right != null) {
queue.offer(node.right);
}
temp.add(node.val);
}
res.add(temp);
}
return res;
}
}
剑指 Offer 32 - III. 从上到下打印二叉树 III
请实现一个函数按照之字形顺序打印二叉树，即第一行按照从左到右的顺序打印，第二层按照从右到左的顺序打印，第三行再按照从左到右的顺序打印，其他行以此类推。
思路：
①按照之字形打印二叉树。广度搜索优先。取巧的方法，设置标志位，隔行对结果进行反转。
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
public List<List<Integer>> levelOrder(TreeNode root) {
List<List<Integer>> res = new ArrayList<>();
if(root == null) return res;
Queue<TreeNode> q = new LinkedList<>();
q.add(root);
List<Integer> temp = new ArrayList<>();
boolean flag = true;
while(!q.isEmpty()) {
int size = q.size();
temp.clear();
for(int i = 0; i < size; i++) {
TreeNode cur = q.poll();
temp.add(cur.val);
if(cur.left != null) q.add(cur.left);
if(cur.right != null) q.add(cur.right);
}
if(flag) {
res.add(new ArrayList(temp));
} else {
Collections.reverse(temp);
res.add(new ArrayList(temp));
}
flag = !flag;
}
return res;
}
}
②利用链表（更快）。当前res的大小为偶数时用addLast方法，为奇数时用addFirst实现倒序。对于第一层，res为0，从左向右；对于第二层，res为1，从右向左。
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
public List<List<Integer>> levelOrder(TreeNode root) {
List<List<Integer>> res = new ArrayList<>();
if(root == null) return res;
Queue<TreeNode> q = new LinkedList<>();
q.add(root);
while(!q.isEmpty()) {
int size = q.size();
LinkedList<Integer> temp = new LinkedList<>();
for(int i = 0; i < size; i++) {
TreeNode cur = q.poll();
if (res.size() % 2 == 0) {
temp.addLast(cur.val);
} else {
temp.addFirst(cur.val);
}
if(cur.left != null) q.add(cur.left);
if(cur.right != null) q.add(cur.right);
}
res.add(temp);
}
return res;
}
}
剑指 Offer 34. 二叉树中和为某一值的路径
输入一棵二叉树和一个整数，打印出二叉树中节点值的和为输入整数的所有路径。从树的根节点开始往下一直到叶节点所经过的节点形成一条路径。
思路：
深度优先搜索。记录经过的节点，遍历到根节点时判断累加和是否为目标值。
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
public List<List<Integer>> pathSum(TreeNode root, int sum) {
List<List<Integer>> res = new ArrayList<>();
if (root == null) return res;
helper(new ArrayList<>(), res, root, sum);
return res;
}
private void helper(List<Integer> list, List<List<Integer>> res, TreeNode root, int sum) {
list.add(root.val);
if (root.left == null && root.right == null) {
int cur = 0;
for (int n : list) {
cur += n;
}
if (cur == sum) {
res.add(new ArrayList<>(list));
return;
}
}
if (root.left != null) {
helper(list, res, root.left, sum);
list.remove(list.size() - 1);
}
if (root.right != null) {
helper(list, res, root.right, sum);
list.remove(list.size() - 1);
}
}
}
②深度优先搜索（更快）。利用链表。
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
LinkedList<List<Integer>> res = new LinkedList();
LinkedList<Integer> path = new LinkedList();
public List<List<Integer>> pathSum(TreeNode root, int sum) {
recur(root,sum);
return res;
}
private void recur(TreeNode root, int tar){
if(root == null){
return;
}
path.add(root.val);
tar-=root.val;
if(tar == 0 && root.left == null && root.right == null){
res.add(new LinkedList(path));
}
recur(root.left,tar);
recur(root.right,tar);
path.removeLast();
}
}
若有收获，就点个赞吧
0 人点赞
