-
【124. Binary Tree Maximum Path Sum 求二叉树最大路径和】 hard DFS 后序遍历
截屏2021-12-13 上午9.39.15.png
思路：四种可能情况： 第一种是root+left，第二种是root+right，第三种是root+left+right，第四种是root。如果当前节点上面还有节点，那它的父节点是不能累加（主要指第三种情况）。所以我们要计算两个最大值：一个是当前节点下最大路径和（断绝希望，用全局变量maxValue更新），另一个是如果要连接父节点时最大的路径和（有希望，用递归函数返回值更新）
相关：DFS 后序遍历
public class Solution {
int maxValue;
public int maxPathSum(TreeNode root) {
maxValue = Integer.MIN_VALUE;
maxPathDown(root);
return maxValue;
}
// 函数返回：以当前结点为根结点，到叶节点的最大路径之和(因此left或者right二选一)
private int maxPathDown(TreeNode node) {
if (node == null) return 0;
int left = Math.max(0, maxPathDown(node.left));
int right = Math.max(0, maxPathDown(node.right));
maxValue = Math.max(maxValue, left + right + node.val);
return Math.max(left, right) + node.val;
}
}
1.2 【112. Path Sum 二叉树的路径和】 easy DFS 先序遍历
Given a binary tree and a sum, determine if the tree has a root-to-leaf path such that adding up all the values along the path equals the given sum.
bool hasPathSum(TreeNode root, int sum) {
if (root == null) return false;
if (root.left == null && root.right == null && root.val == sum ) return true;
return hasPathSum(root.left, sum - root.val) || hasPathSum(root.right, sum - root.val);
}
1.3 【Sum Root to Leaf Numbers 求根到叶节点数字之和】 先序遍历
Given a binary tree containing digits from 0-9 only, each root-to-leaf path could represent a number.
An example is the root-to-leaf path 1->2->3 which represents the number 123.
Find the total sum of all root-to-leaf numbers.
// 解法一：递归的DFS
public int sumNumbers(TreeNode root) {
if (root == null) {
return 0;
}
return sumNumbersHelper(root, 0);
}
private int sumNumbersHelper(TreeNode node, int curVal) {
if (node == null) {
return 0;
}
curVal = curVal * 10 + node.val;
if (node.left == null && node.right == null) {
return curVal;
}
return sumNumbersHelper(node.left, curVal) + sumNumbersHelper(node.right, curVal);
}
// 解法二： 前序遍历的非递归变形
public int sumNumbers(TreeNode root) {
if (root == null) {
return 0;
}
if (root.left == null && root.right == null) {
return root.val;
}
Deque<Pair<TreeNode, Integer>> stack = new ArrayDeque<>();
stack.push(new Pair<>(root, root.val));
int sum = 0;
while (!stack.isEmpty()) {
Pair<TreeNode, Integer> cur = stack.pop();
TreeNode node = cur.getKey();
int num = cur.getValue();
if (node.left == null && node.right == null) {
sum += num;
continue;
}
if (node.right != null) {
stack.push(new Pair<>(node.right, num * 10 + node.right.val));
}
if (node.left != null) {
stack.push(new Pair<>(node.left, num * 10 + node.left.val));
}
}
return sum;
}
1.4 【113. Path Sum II】 DFS + 回溯算法 + 先序遍历
Given the root of a binary tree and an integer targetSum, return all root-to-leaf paths where the sum of the node values in the path equals targetSum. Each path should be returned as a list of the node values, not node references.
A root-to-leaf path is a path starting from the root and ending at any leaf node. A leaf is a node with no children.
public List<List<Integer>> pathSum(TreeNode root, int sum){
List<List<Integer>> result = new LinkedList<List<Integer>>();
List<Integer> currentResult = new LinkedList<Integer>();
pathSum(root,sum,currentResult,result);
return result;
}
public void pathSum(TreeNode root, int sum, List<Integer> currentResult,
List<List<Integer>> result) {
if (root == null)
return;
currentResult.add(new Integer(root.val));
if (root.left == null && root.right == null && sum == root.val) {
result.add(new LinkedList(currentResult));
currentResult.remove(currentResult.size() - 1);//don't forget to remove the last integer
return;
} else {
pathSum(root.left, sum - root.val, currentResult, result);
pathSum(root.right, sum - root.val, currentResult, result);
}
currentResult.remove(currentResult.size() - 1);
}
1.5 【437. Path Sum III】 medium DFS 先序遍历
Given the root of a binary tree and an integer targetSum, return the number of paths where the sum of the values along the path equals targetSum.
The path does not need to start or end at the root or a leaf, but it must go downwards (i.e., traveling only from parent nodes to child nodes).
// 第一种方法：DFS 先序遍历
int pathSum(TreeNode* root, int sum) {
int res = 0;
vector<TreeNode*> out;
helper(root, sum, 0, out, res);
return res;
}
// curSum： 从根节点到当前节点的路净之和
// out：依次保存了从根节点到当前节点的各个节点
void helper(TreeNode* node, int sum, int curSum, vector<TreeNode*>& out, int& res) {
if (!node) return;
curSum += node->val;
out.push_back(node);
if (curSum == sum) ++res;
int t = curSum;
for (int i = 0; i < out.size() - 1; ++i) { // 从根节点开始剪枝
t -= out[i]->val;
if (t == sum) ++res;
}
helper(node->left, sum, curSum, out, res);
helper(node->right, sum, curSum, out, res);
out.pop_back();
}
// 第二种方法，利用hashmap的记录功能，减少重复计算
int count;
public int pathSum(TreeNode root, int targetSum) {
HashMap<Integer, Integer>hs = new HashMap<>();
count = 0;
return pathSum(root, hs, targetSum, 0);
}
public int pathSum(TreeNode root, HashMap<Integer, Integer>hs, int target, int sum){
if(root == null)return 0;
sum +=root.val;
if(sum-target == 0)count++;
if(hs.containsKey(sum-target)){
count+=hs.get(sum-target);
}
hs.put(sum, hs.getOrDefault(sum, 0)+1);
pathSum(root.left, hs, target, sum);
pathSum(root.right, hs, target, sum);
if(hs.get(sum)>1)
hs.put(sum,hs.get(sum)-1);
else hs.remove(sum);
return count;
}
1.6 【687 . Longest Univalue Path】 medium 后序遍历
Given the root of a binary tree, return the length of the longest path, where each node in the path has the same value. This path may or may not pass through the root.
The length of the path between two nodes is represented by the number of edges between them.
class Solution {
int ans;
public int longestUnivaluePath(TreeNode root) {
ans = 0;
arrowLength(root);
return ans;
}
public int arrowLength(TreeNode node) {
if (node == null) return 0;
int left = arrowLength(node.left)
int right = arrowLength(node.right);
int arrowLeft = 0, arrowRight = 0;
if (node.left != null && node.left.val == node.val) {
arrowLeft += left + 1;
}
if (node.right != null && node.right.val == node.val) {
arrowRight += right + 1;
}
ans = Math.max(ans, arrowLeft + arrowRight);
return Math.max(arrowLeft, arrowRight);
}
}
- 【684. Redundant Connection】Medium DFS+回溯
题目：给定一个图，其中只有一条边是多余的，去掉它就能变成一颗无向树。请找到这个边
分析：考察 findFather的能力。写一个函数，用于寻找、更新 父节点
// find father的写法
class Solution {
public int[] findRedundantConnection(int[][] edges) {
int[] parent = new int[2001];
for (int i = 0; i < parent.length; i++) parent[i] = i;
for (int[] edge: edges){
int f = edge[0], t = edge[1];
if (find(parent, f) == find(parent, t)) return edge;
else parent[find(parent, f)] = find(parent, t);
}
return new int[2];
}
private int find(int[] parent, int f) {
if (f != parent[f]) {
parent[f] = find(parent, parent[f]);
}
return parent[f];
}
}
// 邻接表的写法
public int[] findRedundantConnection(int[][] edges) {
List<List<Integer>> graph = new ArrayList<>();
int n = edges.length;
for(int i=0;i<n;i++) {
graph.add(new ArrayList<>());
}
boolean[] visited = new boolean[n];
// question: why this answer satisfy the requirement of the problem:
// Return an edge that can be removed so that the resulting graph is a tree of n nodes. If there are multiple answers, return the answer that occurs last in the input.
for(int[] edge: edges) {
int u = edge[0]-1;
int v = edge[1]-1;
if(graph.get(u).size()>0 && graph.get(v).size()>0) {
if(DFS(u,v,graph,visited)){
return edge;
}
}
graph.get(u).add(v);
graph.get(v).add(u);
}
return null;
}
private boolean DFS(int entry,int target,List<List<Integer>> graph, boolean[] visited) {
if(entry==target){
return true;
}
visited[entry]=true;
boolean res = false;
List<Integer> adj = graph.get(entry);
for(int index: adj){
if(visited[index]==false) {
res = res || DFS(index,target,graph,visited);
}
}
visited[entry]=false;
return res;
}
- 【Recover Binary Search Tree】——中序遍历 Medium
题目：Two elements of a binary search tree (BST) are swapped by mistake.
Recover the tree without changing its structure.
举例：
Input: [3,1,4,null,null,2]
3
/
1 4
/
2
Output: [2,1,4,null,null,3]
2
/
1 4
/
3
分析：如果是一颗 搜索二叉树，全部都是左<跟<右，这样的中序遍历结果就完全是小->大。
代码：
public class Solution {
TreeNode firstElement = null;
TreeNode secondElement = null;
// The reason for this initialization is to avoid null pointer exception in the first comparison when prevElement has not been initialized
TreeNode prevElement = new TreeNode(Integer.MIN_VALUE);
public void recoverTree(TreeNode root) {
// In order traversal to find the two elements
traverse(root);
// Swap the values of the two nodes
int temp = firstElement.val;
firstElement.val = secondElement.val;
secondElement.val = temp;
}
private void traverse(TreeNode root) {
if (root == null)
return;
traverse(root.left);
// Start of "do some business",
// If first element has not been found, assign it to prevElement (refer to 6 in the example above)
if (firstElement == null && prevElement.val >= root.val) {
firstElement = prevElement;
}
// If first element is found, assign the second element to the root (refer to 2 in the example above)
if (firstElement != null && prevElement.val >= root.val) {
secondElement = root;
}
prevElement = root;
// End of "do some business"
traverse(root.right);
}
- 【Graph Valid Tree 图是否是树】DFS 临界表的实现
这道题给了我们一个无向图，让我们来判断其是否为一棵树
例子：
Given n = 5 and edges = [[0, 1], [0, 2], [0, 3], [1, 4]], return true.
Given n = 5 and edges = [[0, 1], [1, 2], [2, 3], [1, 3], [1, 4]], return false.
思路：
利用DFS 或者 BFS遍历，判断（1）所有节点是否都可visit到 （2）是否有节点 可能被多次访问。为了防止回到上一节点，需要在dfs函数 带上参数——pre。
DFS :
public boolean validTree(int n, int[][] edges) {
HashMap<Integer, ArrayList<Integer>> map = new HashMap<Integer, ArrayList<Integer>>();
for(int i=0; i<n; i++){
ArrayList<Integer> list = new ArrayList<Integer>();
map.put(i, list);
}
for(int[] edge: edges){
map.get(edge[0]).add(edge[1]);
map.get(edge[1]).add(edge[0]);
}
boolean[] visited = new boolean[n];
if(!isNotVisitedDFS(0, -1, map, visited))
return false;
for(boolean b: visited){
if(!b)
return false;
}
return true;
}
public boolean isNotVisitedDFS(int curr, int parent, HashMap<Integer, ArrayList<Integer>> map, boolean[] visited){
if(visited[curr])
return false;
visited[curr] = true;
for(int i: map.get(curr)){
if(i!=parent && !isNotVisitedDFS(i, curr, map, visited)){
return false;
}
}
return true;
}
BFS —— 借助queue
public boolean validTree(int n, int[][] edges) {
HashMap<Integer, ArrayList<Integer>> map = new HashMap<Integer, ArrayList<Integer>>();
for(int i=0; i<n; i++){
ArrayList<Integer> list = new ArrayList<Integer>();
map.put(i, list);
}
for(int[] edge: edges){
map.get(edge[0]).add(edge[1]);
map.get(edge[1]).add(edge[0]);
}
boolean[] visited = new boolean[n];
LinkedList<Integer> queue = new LinkedList<Integer>();
queue.offer(0);
while(!queue.isEmpty()){
int top = queue.poll();
if(visited[top])
return false;
visited[top]=true;
for(int i: map.get(top)){
if(!visited[i])
queue.offer(i);
}
}
for(boolean b: visited){
if(!b)
return false;
}
return true;
}
- 【Binary Tree Cameras】 Hard —— BFS 后续遍历
题目：Given a binary tree, we install cameras on the nodes of the tree.
Each camera at a node can monitor its parent, itself, and its immediate children.
Calculate the minimum number of cameras needed to monitor all nodes of the tree.
分析：后续遍历。当前节点需要放置camera的两种情况：
(1) 如果left or right没有被监控到
(2) 如果father=null(意味着0可能被father监控) && 本身没有被监控
int ans;
Set<TreeNode> covered;
public int minCameraCover(TreeNode root) {
ans = 0;
covered = new HashSet();
covered.add(null);
dfs(root, null);
return ans;
}
public void dfs(TreeNode node, TreeNode par) {
if (node != null) {
dfs(node.left, node);
dfs(node.right, node);
if (par == null && !covered.contains(node) ||
!covered.contains(node.left) ||
!covered.contains(node.right)) {
ans++;
covered.add(node);
covered.add(par);
covered.add(node.left);
covered.add(node.right);
}
}
}
-
Sum of Distances in Tree——DFS
截屏2021-11-27 上午11.22.29.png
public int[] sumOfDistancesInTree(int N, int[][] edges) {
if (N == 1) {
return new int[N];
}
if (N == 2) {
return new int[]{1, 1};
}
List<int[]>[] graph = new ArrayList[N];
for (int i = 0; i < N; i++) {
graph[i] = new ArrayList<>();
}
for (int i = 0; i < edges.length; i++) {
// [0] = to [1] = sum [2] = num
graph[edges[i][0]].add(new int[]{edges[i][1], 0, 0});
graph[edges[i][1]].add(new int[]{edges[i][0], 0, 0});
}
int[] result = new int[N];
boolean[] seen = new boolean[N];
for (int i = 0; i < N; i++) {
result[i] = dfs(graph, i, seen)[0];
}
return result;
}
private int[] dfs(List<int[]>[] graph, int i, boolean[] seen) {
seen[i] = true;
int sum = 0;
int num = 1;
for (int[] adj : graph[i]) {
if (!seen[adj[0]]) {
if (adj[1] == 0 && adj[2] == 0) {
int[] res = dfs(graph, adj[0], seen);
adj[1] = res[0];
adj[2] = res[1];
}
sum += (adj[1] + adj[2]);
num += adj[2];
}
}
seen[i] = false;
return new int[]{sum, num};
}
- 【树的后续遍历 非递归】
第一种写法：/**- 思路：
- 1、使用两个栈来实现后续遍历
- 2、栈s1，依次遍历根、左、右
- 3、最后将s2完整弹出
*/
public ArrayList<Integer> postorderTraversalByTwoStack(TreeNode root) {
ArrayList<Integer> retList = new ArrayList<>();
if (root == null) {
return retList;
}
// 初始化s1 s2
Stack<TreeNode> s1 = new Stack<>();
s1.push(root);
Stack<TreeNode> s2 = new Stack<>();
TreeNode curNode;
// s1中节点弹出后，压入s2，左右孩子节点依次压入s1
while (!s1.empty()) {
curNode = s1.pop();
s2.push(curNode);
// 依次压入左右孩子，s1弹出元素顺序为右左，s2入栈顺序为右左，保证s2出栈顺序为左右
if (curNode.left != null) {
s1.push(curNode.left);
}
if (curNode.right != null) {
s1.push(curNode.right);
}
}
// s2中元素出栈，转移到retList
while (!s2.empty()) {
retList.add(s2.pop().val);
}
return retList;
}
第二种写法：只用一个stack. while(!stack.empty())的写法，一次外层遍历，只会压栈一次。核心要保证根结点在左孩子和右孩子访问之后才能访问，因此对于任一结点P，先将其入栈。如果P不存在左孩子和右孩子，则可以直接访问它；或者P存在左孩子或者右孩子，但是其左孩子和右孩子都已被访问过了，则同样可以直接访问该结点。若非上述两种情况，则将P的右孩子和左孩子依次入栈，这样就保证了每次取栈顶元素的时候，左孩子在右孩子前面被访问，左孩子和右孩子都在根结点前面被访问
public static ArrayList postOrder1(TreeNode root){
ArrayList alist = new ArrayList();
Stack<TreeNode> stack = new Stack<TreeNode>();
if(root == null)
return alist;
TreeNode cur,pre = null;
stack.push(root);
while(!stack.empty()){
cur = stack.peek();
if((cur.left == null && cur.right == null) || (pre != null && (cur.left == pre || cur.right == pre))){
TreeNode temp = stack.pop();
alist.add(temp.val);
pre = temp;
}
else{
if(cur.right != null)
stack.push(cur.right);
if(cur.left != null)
stack.push(cur.left);
}
}
return alist;
}
第三种写法：while (root != null || !stack.isEmpty())的形式，外层遍历一次，会将路线左左左到底。然后弹出节点root，如果没有右节点或者右节点已经访问完毕，则可以访问root节点；不然就重新压栈，往右走一步
public List<Integer> postorderTraversal(TreeNode root) {
List<Integer> res = new ArrayList<Integer>();
if (root == null) {
return res;
}
Deque<TreeNode> stack = new LinkedList<TreeNode>();
TreeNode prev = null;
while (root != null || !stack.isEmpty()) {
while (root != null) {
stack.push(root);
root = root.left;
}
root = stack.pop();
if (root.right == null || root.right == prev) {
res.add(root.val);
prev = root;
root = null;
} else {
stack.push(root);
root = root.right;
}
}
return res;
}
- Validate Binary Search Tree——中序遍历的变形
二叉搜索树的中序遍历结果，就是小->大。
所以可以利用非递归形式的二叉搜索过程，解决很多问题，例如本题
代码：
public boolean isValidBST(TreeNode root) {
if(root == null)
return true;
Stack<TreeNode> stack = new Stack<TreeNode>();
TreeNode pre = null;
while(root!=null || !stack.isEmpty()){
while(root != null){
stack.push(root);
root = root.left;
}
root = stack.pop();
if(pre != null && pre.val >= root.val){
return false;
}
pre = root;
root = root.right;
}
return true;
}
问题变形：
寻找树的kth smallest数值：
public int kthSmallest(TreeNode root, int k) {
Stack<TreeNode> stack = new Stack<>();
while(root != null || !stack.isEmpty()) {
while(root != null) {
stack.push(root);
root = root.left;
}
root = stack.pop();
if(--k == 0) break;
root = root.right;
}
return root.val;
}
问题变形： 如何判断是否是满二叉树？
那么如何判断一棵二叉树是否为完全二叉树呢? 按照下面的标准 :
按照层次遍历的顺序遍历二叉树，每一层从左到右；
如果当前结点有右孩子但没有左孩子，直接返回false；
如果当前结点不是左右孩子都全(包括两种情况)，那之后的结点必须都为叶节点，否则返回false；
遍历过程中如果没有返回false，就返回true；
//判断一棵二叉树是不是完全二叉树
static boolean isCBT(TreeNode root){
if(root == null)
return true;
Queue<TreeNode>queue = new LinkedList<>();
boolean leaf = false; //如果碰到了 某个结点孩子不全就开始 判断是不是叶子这个过程
queue.add(root);
TreeNode top = null,L = null,R = null;
while(!queue.isEmpty()){
top = queue.poll();
L = top.left; R = top.right;
//第一种情况
if((R != null && L == null))
return false;
//第二种情况 开启了判断叶子的过程 而且又不是叶子 就返回false
if(leaf && (L != null || R != null)) //以后的结点必须是 左右孩子都是null
return false;
if(L != null)
queue.add(L);
//准确的说是 只要孩子不全就开启leaf，
//但是前面已经否定了有右无左的情况，这里只要判断一下右孩子是不是为空就可以了(如果为空就开启leaf)
if(R != null)
queue.add(R);
else
leaf = true;
}
return true;
}
- 公共祖先问题
如果是二叉搜索树，寻找公共祖先。可利用二叉搜索树的特点——左<根<右的特点，进行val值判断
while(root != null){
if(root.val > p.val && root.val > q.val){
//都比根节点值小，去根节点的左子树继续找
root = root.left;
}else if(root.val < p.val && root.val < q.val){
//都比根节点值大，去根节点的右子树继续找
root = root.right;
}else {
//根节点的值大于p而小于q，说明此时的根节点即为最近公共祖先。
return root;
}
}
return null;
如果是普通的二叉树，可以判断左分支是否包含节点？右分支是否包含节点？
public TreeNode isContainPorQ(TreeNode root, TreeNode p ,TreeNode q){
if(root == null)
return null;
if(root.val == p.val || root.val == q.val)
return root;
TreeNode left = isContainPorQ(root.left, p,q);
TreeNode right = isContainPorQ(root.right, p,q);
if(left!=null && right != null){
return root;
}
else if(left !=null){
return left;
}
else if (right != null){
return right;
}
else
return null;
}
- 【662. Maximum Width of Binary Tree】 medium 层次遍历
求二叉树的最大宽度
例子：
1
/
3 2
/ \
5 9
/
6 7
Output: 8
Explanation:The maximum width existing in the fourth level with the length 8 (6,null,null,null,null,null,null,7).
第一种方法：层次遍历，记录每层的第一个节点的index，记录每层最后一个节点的Index，然后做差值
public int widthOfBinaryTree(TreeNode root) {
if(root == null) return 0;
Queue<TreeNode> q = new LinkedList<TreeNode>();
Map<TreeNode, Integer> m = new HashMap<TreeNode, Integer>();
q.offer(root);
m.put(root, 1);
int curW = 0;
int maxW = 0;
while(!q.isEmpty()){
int size = q.size();
int start = 0;
int end = 0;
for(int i = 0; i < size; i++){
TreeNode node = q.poll();
if(i == 0) start = m.get(node);
if(i == size - 1) end = m.get(node);
if(node.left != null){
m.put(node.left, m.get(node) * 2);
q.offer(node.left);
}
if(node.right != null){
m.put(node.right, m.get(node) * 2 + 1);
q.offer(node.right);
}
}
curW = end - start + 1;
maxW = Math.max(curW, maxW);
}
return maxW;
}
第二种方法
class Solution {
public int widthOfBinaryTree(TreeNode root) {
return dfs(root, 0, 1, new ArrayList<Integer>());
}
public int dfs(TreeNode root, int level, int index, List<Integer> starts){
if(root == null)
return 0;
if(starts.size() == level){
starts.add(index);
}
int curentLen = index - starts.get(level)+1; // 当前层的最大宽度
int leftMax = dfs(root.left, level+1, 2*index, starts); // 左节点所在层，从左->左孩子 的最大宽度
int rightMax = dfs(root.right, level+1, 2*index+1, starts); // 右节点所在层，从左->右孩子 的最大宽度
return Math.max(curentLen, Math.max(leftMax,rightMax)); // 求三者最大
}
}
- 利用树的中序遍历+后续遍历，构造二叉树
public TreeNode buildTreePostIn(int[] inorder, int[] postorder) {
if (inorder == null || postorder == null || inorder.length != postorder.length)
return null;
HashMap<Integer, Integer> hm = new HashMap<Integer,Integer>();
for (int i=0;i<inorder.length;++i)
hm.put(inorder[i], i);
return buildTreePostIn(inorder, 0, inorder.length-1, postorder, 0,
postorder.length-1,hm);
}
private TreeNode buildTreePostIn(int[] inorder, int is, int ie, int[] postorder, int ps, int pe,
HashMap<Integer,Integer> hm){
if (ps>pe || is>ie) return null;
TreeNode root = new TreeNode(postorder[pe]);
int ri = hm.get(postorder[pe]);
TreeNode leftchild = buildTreePostIn(inorder, is, ri-1, postorder, ps, ps+ri-is-1, hm);
TreeNode rightchild = buildTreePostIn(inorder,ri+1, ie, postorder, ps+ri-is, pe-1, hm);
root.left = leftchild;
root.right = rightchild;
return root;
}
-
Populating Next Right Pointers in Each Node
截屏2021-11-27 上午11.34.00.png
问题：二叉树节点 增加了next指针，指向同层的下一个。
struct Node {
int val;
Node *left;
Node *right;
Node *next;
}
请把next指针补全
解法1——层次遍历方法： 时间 O(N) 空间 O(N)
public class Solution {
public void connect(TreeLinkNode root) {
TreeLinkNode head = root;
while(head != null){
// 记录当层第一个节点
TreeLinkNode tmpHead = head;
// 开始链接下一层
while(head != null){
//链接左节点
if(head.left != null) head.left.next = head.right;
//链接右节点
if(head.right != null) head.right.next = head.next != null ? head.next.left : null;
head = head.next;
}
// 跳到下一层第一个节点
head = tmpHead.left;
}
}
}
解法2——指针法 ： 时间 O(N) 空间 O(1)
public Node connect(Node root) {
if(root == null)
return null;
Node level_start = root;
while(level_start != null){
Node cur = level_start;
while(cur != null){
if(cur.left !=null)
cur.left.next = cur.right;
if(cur.right != null && cur.next != null)
cur.right.next = cur.next.left;
cur = cur.next;
}
level_start = level_start.left;
}
return root;
}
-
Path Sum II——DFS
题目：Given a binary tree and a sum, find all root-to-leaf paths where each path's sum equals the given sum.
例子：
Given the below binary tree and sum = 22,5
/
4 8
/ /
11 13 4
/ \ /
7 2 5 1
Return:
[
[5,4,11,2],
[5,8,4,5]
]
代码：
public List<List<Integer>> pathSum(TreeNode root, int sum){
List<List<Integer>> result = new LinkedList<List<Integer>>();
List<Integer> currentResult = new LinkedList<Integer>();
pathSum(root,sum,currentResult,result);
return result;
}
public void pathSum(TreeNode root, int sum, List<Integer> currentResult,
List<List<Integer>> result) {
if (root == null)
return;
currentResult.add(new Integer(root.val));
if (root.left == null && root.right == null && sum == root.val) {
result.add(new LinkedList(currentResult));
currentResult.remove(currentResult.size() - 1);//don't forget to remove the last integer
return;
} else {
pathSum(root.left, sum - root.val, currentResult, result);
pathSum(root.right, sum - root.val, currentResult, result);
}
currentResult.remove(currentResult.size() - 1);
}
- 【前序遍历 非递归】
第一种写法：while (!s.isEmpty())，一次外层遍历 只压栈和出站一次
public void preOrder(Node head) {
if (head == null) {
return;
}
Stack<Node> s = new Stack<Node>();
s.push(head);
while (!s.isEmpty()) {
Node cur = s.pop();
System.out.println(cur.val);
if (cur.right != null) {
s.push(cur.right);
}
if (cur.left != null) {
s.push(cur.left);
}
}
}
第二种写法：while(p != null || !stack.empty()) 外层循环走一次，就是左左左到底
public static ArrayList preOrder1(TreeNode root){
Stack<TreeNode> stack = new Stack<TreeNode>();
ArrayList alist = new ArrayList();
TreeNode p = root;
while(p != null || !stack.empty()){
while(p != null){
alist.add(p.val);
stack.push(p);
p = p.left;
}
if(!stack.empty()){
TreeNode temp = stack.pop();
p = temp.right;
}
}
return alist;
- 【中序遍历 非递归】
while(p != null || !stack.empty()) 外层循环走一次，就是左左左到底
public static ArrayList inOrder1(TreeNode root){
ArrayList alist = new ArrayList();
Stack<TreeNode> stack = new Stack<TreeNode>();
TreeNode p = root;
while(p != null || !stack.empty()){
while(p != null){
stack.push(p);
p = p.left;
}
if(!stack.empty()){
TreeNode temp = stack.pop();
alist.add(temp.val);
p = temp.right;
}
}
return alist;
}
- 【层次遍历 非递归】
第一种写法：只有一层while循环，queue出队列后，依次将左右节点入队
private static void levelOrder(TreeNode root) {
Queue<TreeNode> queue = new LinkedList<TreeNode>();
if(root == null)
return;
queue.offer(root);
while(!queue.isEmpty()){
TreeNode temp = queue.poll();
System.out.print(temp.val + " ");
if(temp.left != null)
queue.offer(temp.left);
if(temp.right != null)
queue.offer(temp.right);
}
第二种写法：双层while。 外层while遍历层，内层while遍历同层的各个节点，把left+right入队
public List<List<Integer>> levelOrder(TreeNode root) {
List<List<Integer>> resultList=new ArrayList<>();
int levelNum=0;//记录某层具有多少个节点
Queue<TreeNode> treeQueue=new LinkedList<>();
treeQueue.add(root);
while(!treeQueue.isEmpty()){
levelNum=treeQueue.size();
List<Integer> levelList=new ArrayList<>();
while(levelNum>0){
TreeNode tempNode=treeQueue.poll();
if(tempNode!=null){
levelList.add(tempNode.val);
treeQueue.add(tempNode.left);
treeQueue.add(tempNode.right);
}
levelNum--;
}
if(levelList.size()>0)
resultList.add(levelList);
}
return resultList;
}
网友评论