文章目录
JZ32 从上往下打印二叉树
题目描述
思路详解
二叉树的层次遍历就是按照从上到下每行，然后每行中从左到右依次遍历，得到的二叉树的元素值。对于层次遍历，我们通常会使用队列来辅助：
因为队列是一种先进先出的数据结构，我们依照它的性质，如果从左到右访问完一行节点，并在访问的时候依次把它们的子节点加入队列，那么它们的子节点也是从左到右的次序，且排在本行节点的后面，因此队列中出现的顺序正好也是从左到右，正好符合层次遍历的特点。
代码与结果
import java.util.*; public class Solution { public ArrayList<Integer> PrintFromTopToBottom(TreeNode root) { ArrayList<Integer> res = new ArrayList(); if (root == null) //如果是空，则直接返回空数组 return res; //队列存储，进行层次遍历 Queue<TreeNode> q = new ArrayDeque<TreeNode>(); q.offer(root); while (!q.isEmpty()) { TreeNode cur = q.poll(); res.add(cur.val); //若是左右孩子存在，则存入左右孩子作为下一个层次 if (cur.left != null) q.add(cur.left); if (cur.right != null) q.add(cur.right); } return res; } }
JZ33 二叉搜索树的后序遍历序列
题目描述
思路详解
思路：单调栈首先我们需要按照题目给出列表的逆序进行遍历，这样我们的遍历视角转成了[根一右子树—左子树]。假定原输入列表的顺序为[tn,tn1,t2,t1,则该逆序后列表内容to,t,t2,tn]有如下特性：
1.当t<ti+1时，说明节点t+1是t的右子节点
2.当t:>ti+1时，说明节点ti+1是已经遍历过的所有节点中比t+1大的目最接近t+1的节点的左子节点，设t+1对应的该父节点为root。同时要满足ti+1,ti+2,tn都要比root小。
3.根据我们推理的以上性质（加粗部分），用单调栈工具进行操作，如果能找到不符合以上性质的矛盾点，则返回fa1se,如果上述性质都满足，则返回true
代码与结果
import java.util.*; public class Solution { public boolean VerifySquenceOfBST(int [] sequence) { // 处理序列为空情况 if(sequence.length == 0) return false; Stack<Integer> s = new Stack<>(); int root = Integer.MAX_VALUE; // 以根，右子树，左子树顺序遍历 for(int i = sequence.length - 1; i >= 0; i--) { // 确定根后一定是在右子树节点都遍历完了，因此当前sequence未遍历的节点中只含左子树，左子树的节点如果>root则说明违背二叉搜索的性质 if(sequence[i] > root) return false; // 进入左子树的契机就是sequence[i]的值小于前一项的时候，这时可以确定root while(!s.isEmpty() && s.peek() > sequence[i]) { root = s.pop(); } // 每个数字都要进一次栈 s.add(sequence[i]); } return true; } }
JZ34 二叉树中和为某一值的路径(二)
题目描述
思路详解
我们从根节点开始向左右子树进行递归，递归函数中需要处理的是：
当前的路径path要更新
当前的目标值expectNumber要迭代，减去当前节点的值
若当前节点是叶子节点，考虑是否满足路径的期待值，并考虑是否将路径添加到返回列表中
代码与结果
import java.util.*; public class Solution { private ArrayList<ArrayList<Integer>> ret = new ArrayList<>(); private LinkedList<Integer> path = new LinkedList<>(); void dfs(TreeNode root, int number) { // 处理树为空 if (root == null) return; // 路径更新 path.add(root.val); // number更新 number -= root.val; // 如果递归当前节点为叶子节点且该条路径的值已经达到了expectNumber，则更新ret if(root.left == null && root.right == null && number == 0) { ret.add(new ArrayList<>(path)); } // 左右子树递归 dfs(root.left, number); dfs(root.right, number); path.removeLast(); } public ArrayList<ArrayList<Integer>> FindPath(TreeNode root,int expectNumber) { dfs(root, expectNumber); return ret; } }
