vlambda博客
学习文章列表

public class TreeNode {      int val;      TreeNode left;      TreeNode right;      TreeNode() {}      TreeNode(int val) { this.val = val; }      TreeNode(int val, TreeNode left, TreeNode right) {          this.val = val;          this.left = left;          this.right = right;      }  }

class Solution {  public List<Integer> preorderTraversal(TreeNode root) { ArrayList<Integer> ans = new ArrayList<>(); preorder(root,ans); return ans; }
 public void preorder(TreeNode root,ArrayList<Integer> ans){ //1. 递归终止条件 if(root==null) return;        //2. 将根节点元素的值添加进入链表中 ans.add(root.val);        //3. 递归遍历左子节点 preorder(root.left,ans); //4. 递归遍历右子节点 preorder(root.right,ans); }}

class Solution { public List<Integer> preorderTraversal(TreeNode root) {        //用来存放结果 ArrayList<Integer> ans = new ArrayList<>();        //递归结束条件 if(root == null) return ans; //前序遍历，先将根节点加入到链表中 ans.add(root.val); //遍历所有的左子节点，并将其装入到集合中 ans.addAll(preorderTraversal(root.left));        //遍历所有的右子节点，并将其装入到集合中 ans.addAll(preorderTraversal(root.right)); //返回前序遍历结果 return ans; }}

class Solution { public List<Integer> preorderTraversal(TreeNode root) { //存放结果 ArrayList<Integer> ans = new ArrayList<>();        //存放中间节点（所有的左子节点） Deque<TreeNode> stack = new ArrayDeque<>(); //1. 当root不为空 or 栈不为空 while(root!=null||!stack.isEmpty()){            //2. 找到某个节点为跟的路径的所有左子节点，并将节点值添加到链表中 while(root!=null){ ans.add(root.val); stack.addLast(root); root = root.left; }           //3. 从栈弹出一个节点，让root赋值为该节点的右子节点 TreeNode node = stack.pollLast(); root = node.right; }        //4. 返回结果链表 return ans; }}

class Solution { public List<Integer> inorderTraversal(TreeNode root) { ArrayList<Integer> ans = new ArrayList<>(); inorder(root,ans); return ans; } public void inorder(TreeNode root,ArrayList<Integer> ans){ if(root == null) return; //1. 递归遍历左子节点 inorder(root.left,ans); //2. 再遍历根节点 ans.add(root.val); //3. 最后遍历右子节点 inorder(root.right,ans); }}

class Solution { public List<Integer> inorderTraversal(TreeNode root) { ArrayList<Integer> ans = new ArrayList<>(); //递归终止条件 if(root == null) return ans; //1. 容器中装入所有左子节点，并将左子节点加入到ans中 ans.addAll(inorderTraversal(root.left)); //2. 遍历添加根节点 ans.add(root.val); //3. 容器中装入所有右子节点，并将右子节点加入到ans中 ans.addAll(inorderTraversal(root.right)); //返回最后结果 return ans; }}

class Solution { public List<Integer> inorderTraversal(TreeNode root) { ArrayList<Integer> ans = new ArrayList<>(); Deque<TreeNode> stack = new ArrayDeque<>(); //1. 当root不为空 or 链表不为空时才可进入while循环 while(root!=null||!stack.isEmpty()){ //2. 当root不为空时，进入循环不断寻找某枝节上的左子节点 while(root!=null){ stack.add(root); root = root.left; } //3. 弹出栈顶元素 root = stack.pollLast(); //4. 将其加入到ans链表中 ans.add(root.val); //5. 遍历弹出节点的右分支 root = root.right; } return ans; }}

class Solution { public List<Integer> postorderTraversal(TreeNode root) { ArrayList<Integer> ans = new ArrayList<>(); posorder(root,ans); return ans; }
 public void posorder(TreeNode root,ArrayList<Integer> ans){ //1. 递归终止条件 if(root == null) return; //2. 先遍历左子节点 posorder(root.left,ans); //3. 再遍历右子节点 posorder(root.right,ans); //4. 最后遍历根节点 ans.add(root.val); }}

class Solution { public List<Integer> postorderTraversal(TreeNode root) { ArrayList<Integer> ans = new ArrayList<>(); //递归终止条件 if(root == null) return ans; //1. 将左子节点全部装入到集合中，遍历左子节点并将左子节点的val加入到ans链表中 ans.addAll(postorderTraversal(root.left)); //2. 将右子节点全部装入到集合中，遍历右子节点并将右子节点的val加入到ans链表中 ans.addAll(postorderTraversal(root.right)); //3. 遍历根节点 ans.add(root.val); //4. 返回ans链表 return ans; }}

class Solution { public List<Integer> postorderTraversal(TreeNode root) { ArrayList<Integer> ans = new ArrayList<>(); Deque<TreeNode> stack = new ArrayDeque<>(); //保存上次的root节点，用来判断右子节点是否被遍历了 TreeNode prev = null; //1. 当root不为空 or 栈不为空进入循环 while(root!=null || !stack.isEmpty()){ //2. 迭代的通式，先找到root节点对应的左子叶节点 while(root!=null){ //将每次的左子节点存入栈中 stack.addLast(root); root = root.left; } //3. 弹出栈顶节点 root = stack.pollLast(); //4. 当root.right为空表示当前根节点的右节点是空的，可以直接将其加入到ans链表中，并将prev赋值为当前的root //当root.right == prev时，表示前面我们已经遍历过当前根节点的右子节点了，因此，只需将当前节点加入ans链表即可 if(root.right==null || root.right==prev){ ans.add(root.val); prev = root; root = null; //5. 否则，说明当前root节点的右子节点存在且还没有被遍历  }else{ //先将根节点加回到栈中 stack.addLast(root); //然后遍历右子节点所在的分支 root = root.right; } } //6. 返回ans链表 return ans; }}

class Solution {    public List<List<Integer>> levelOrder(TreeNode root) {        Deque<TreeNode> queue = new ArrayDeque<TreeNode>(); ArrayList<List<Integer>> ans = new ArrayList<>(); //1. 如果root不为空，则加入到queue中，表示第一层的节点 if(root!=null) queue.addLast(root); //2. 如果queue不为空，则继续循环遍历 while(!queue.isEmpty()){ //3. 获得当前层的节点数，并将其按FIFO顺序加入到list链表中，并判断出队列的节点是否有左右子节点，将其加入queue中 int size = queue.size(); //这里每次进入while循环都会创建一个链表用于存储该层节点 List<Integer> list = new ArrayList<>(); for(int i=size;i>0;i--){ TreeNode node = stack.pollFirst(); list.add(node.val); if(node.left!=null) queue.addLast(node.left); if(node.right!=null) queue.addLast(node.right); } //4. 将每层节点装入到汇总链表中 ans.add(list); } return ans; }}

class Solution { public TreeNode buildTree(int[] preorder, int[] inorder) { return buildTreeHelper(preorder, 0, preorder.length, inorder, 0, inorder.length); }  public TreeNode buildTreeHelper(int[] preorder, int p_start, int p_end, int[] inorder, int i_start, int i_end){ //1. 递归终止条件，说明已经将前序数组遍历完成了 if(p_start == p_end) return null; //2. preorder第一个元素就是根节点，并创建新树的根节点 int root_val = preorder[p_start]; TreeNode root = new TreeNode(root_val); //3. 在中序数组中找到当前根节点，从当前的i_start开始，从i_end结束 int i_root_val = 0; for(int i=i_start;i<i_end;i++){ if(root_val == inorder[i]){ i_root_val = i; break; } } //4. 计算当前根左子节点的个数 int leftNum = i_root_val-i_start; //5. 利用分治思想分别递归构造左子树和右子树 root.left = buildTreeHelper(preorder, p_start+1, p_start + leftNum + 1, inorder, i_start, i_root_val); root.right = buildTreeHelper(preorder, p_start + leftNum + 1, p_end, inorder, i_root_val + 1, i_end); //6. 返回当前新树的根节点 return root; }}

class Solution { private HashMap<Integer,Integer> map = new HashMap<>(); public TreeNode buildTree(int[] preorder, int[] inorder) { //将中序数组的元素和对应的下标存入到HashMap中  for(int i=0;i<inorder.length;i++){ map.put(inorder[i],i); } return buildTreeHelper(preorder, 0, preorder.length, inorder, 0, inorder.length, map); }     public TreeNode buildTreeHelper(int[] preorder, int p_start, int p_end, int[] inorder, HashMap<Integer,Integer> map){
      //1. 递归终止条件，说明已经将前序数组遍历完成了 if(p_start == p_end)      return null; //2. preorder第一个元素就是根节点，并创建新树的根节点 int root_val = preorder[p_start]; TreeNode root = new TreeNode(root_val); //3. 利用HashMap从中序数组中找到当前根节点 int i_root_val = map.get(root_val); //4. 计算当前根左子节点的个数 int leftNum = i_root_val-i_start; //5. 分别递归构造左子树和右子树 root.left = buildTreeHelper(preorder, p_start+1, p_start + leftNum + 1, inorder, i_start, i_root_val, map); root.right = buildTreeHelper(preorder, p_start + leftNum + 1, p_end, inorder, i_root_val + 1, i_end, map); //6. 返回当前新树的根节点 return root; }}

public TreeNode buildTree(int[] preorder, int[] inorder) { return buildTreeHelper(preorder, inorder, (long)Integer.MAX_VALUE + 1);}int pre = 0;int in = 0;private TreeNode buildTreeHelper(int[] preorder, int[] inorder, long stop) { //到达末尾返回 null if(pre == preorder.length){ return null; } //到达停止点返回 null //当前停止点已经用了，in 后移 if (inorder[in] == stop) { in++; return null; } int root_val = preorder[pre++]; TreeNode root = new TreeNode(root_val);  //左子树的停止点是当前的根节点 root.left = buildTreeHelper(preorder, inorder, root_val); //右子树的停止点是当前树的停止点 root.right = buildTreeHelper(preorder, inorder, stop); return root;}

class Solution { public TreeNode buildTree(int[] preorder, int[] inorder){ //前序数组为空 or 长度为0则返回 null if(preorder==null || preorder.length==0){ return null; } Deque<TreeNode> stack = new LinkedList<TreeNode>(); //建立新树根节点 TreeNode root = new TreeNode(preorder[0]); stack.push(root); //记录中序遍历的下标，主要用于判断是否是左子节点，后者是某个节点的右子节点 int inorderindex = 0; //1. 遍历循环前序数组，然后用栈和中序数组来判断节点是左子节点，还是某个节点的右子节点 for(int i=1;i<preorder.length;i++){ int preorderval = preorder[i]; TreeNode node = stack.peek(); //1. 如果栈顶元素不等于中序遍历inorderindex下标的节点，则表明当前节点是左子树上的节点 //栈中前者的节点比后者的根级别高，也就是越靠近root节点 if(node.val!=inorder[inorderindex]){ node.left = new TreeNode(preorderval); stack.push(node.left); }else{ //2. 当栈顶元素等于inorderindex的下标时，则说明左子树遍历完成，开始遍历右子树了 //判断右子节点属于哪个节点的右子节点的时候，我们发现前面入栈的左子树的节点的顺序，刚好在中序遍历是反过来的 //当我们从栈中弹出的第一个节点肯定和中序数组的第一个节点相同，就这样不断弹栈，然后将inorderindex向后移动，直到第一个不相同的节点为止，那么在中序遍历中，该节点肯定是第一个右子节点，该右子节点就是最后一个出栈的节点的右子节点 while(!stack.isEmpty()&&stack.peek().val==inorder[inorderindex]){ node = stack.pop(); inorderindex++; } //3. 将右子节点存入新树之中，node是while循环中最后一个出栈的节点，并将右节点放入栈中 node.right = new TreeNode(preorderval); stack.push(node.right); } } return root; }}

class Solution { public TreeNode constructFromPrePost(int[] pre, int[] post) { //1. 创建新二叉树的root节点  int len = pre.length; if(len == 0) return null; TreeNode root = new TreeNode(pre[0]); if(len == 1) return root; //2. 计算左子节点的长度，如果post[i] = pre[1], 则说明我们找到了左子节点的长度 //那么在pre前序数组中，左子节点的长度范围为[1,L+1]，在post后续数组中，左子节点的长度范围为[0,L]  int L = 0; for(int i=0;i<len;++i){ if(post[i] == pre[1]) L = i+1; } //3. 用分治思想，递归找到左分支和右分支 root.left = constructFromPrePost(Arrays.copyOfRange(pre,1,L+1),Arrays.copyOfRange(post,0,L)); root.right = constructFromPrePost(Arrays.copyOfRange(pre,L+1,len),Arrays.copyOfRange(post,L,len)); //4. 返回root根节点 return root; }}

class Solution { private HashMap<Integer,Integer> map = new HashMap<>(); public TreeNode constructFromPrePost(int[] pre, int[] post) { for(int i=0;i<post.length;++i){ map.put(post[i],i); } return makeTree(pre,post,map); }
 public TreeNode makeTree(int[] pre,int[] post,HashMap<Integer,Integer> map){ //1. 创建新二叉树的root节点  int len = pre.length; if(len == 0) return null;  TreeNode root = new TreeNode(pre[0]); if(len == 1) return root; //2. 计算左子节点的长度，如果post[i] = pre[1], 则说明我们找到了左子节点的长度 //那么在pre前序数组中，左子节点的长度范围为[1,L+1]，在post后续数组中，左子节点的长度范围为[0,L]  int L = 0; L = map.getOrDefault(pre[1],-1)+1; //3. 用分治思想，递归找到左分支和右分支 root.left = makeTree(Arrays.copyOfRange(pre,1,L+1),Arrays.copyOfRange(post,0,L),map); root.right = makeTree(Arrays.copyOfRange(pre,L+1,len),Arrays.copyOfRange(post,L,len),map); //4. 返回root根节点 return root; }}

/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */class Solution { private HashMap<Integer,Integer> map = new HashMap<>(); public TreeNode constructFromPrePost(int[] pre, int[] post) { return makeTree(pre,post,0,0,pre.length); }
 public static TreeNode makeTree(int[] pre,int[] post,int pr_start,int po_start, int len){ if(len==0) return null; TreeNode root = new TreeNode(pre[pr_start]); if(len==1) return root; //1. 计算左子节点的长度 int L =1; for(;L<len;++L){ if(post[po_start+L-1] == pre[pr_start+1]){ break; } }  /** * 2. 递归遍历每一个节点的左右子节点，有则返回，没有则返回null * pr_start表示每次pre开始的位置，po_start表示post数组开始的位置，len表示当前数组的长度 * 记录数组的起始点和长度就可以变向的得到数组的副本 */ root.left = makeTree(pre,post,pr_start+1,po_start,L); root.right = makeTree(pre,post,pr_start+L+1,po_start+L,len-L-1); //3. 返回root节点 return root; }}

class Solution { private HashMap<Integer,Integer> map = new HashMap<>(); public TreeNode constructFromPrePost(int[] pre, int[] post) { for(int i=0;i<pre.length;i++){ map.put(post[i],i); } return makeTree(pre,post,0,0,pre.length,map); }
 public static TreeNode makeTree(int[] pre,int[] post,int pr_start,int po_start, int len,Map<Integer,Integer> map){ if(len==0) return null; TreeNode root = new TreeNode(pre[pr_start]); if(len==1) return root; //计算左子节点的长度 int L = map.get(pre[pr_start+1])-po_start+1; /** * 递归遍历每一个节点的左右子节点，有则返回，没有则返回null * pr_start表示每次pre开始的位置，po_start表示post数组开始的位置，len表示当前数组的长度 * 记录数组的起始点和长度就可以变向的得到数组的副本 */ root.left = makeTree(pre,post,pr_start+1,po_start,L,map); root.right = makeTree(pre,post,pr_start+L+1,po_start+L,len-L-1,map); return root; }}

class Solution { public TreeNode buildTree(int[] inorder, int[] postorder) { return makeTree(inorder, postorder,0,0,postorder.length); }
 public TreeNode makeTree(int[] inorder, int[] postorder,int i_start,int p_start,int len){ /** * 1. 递归终止条件 * len = 0，说明上次递归已经遍历到了某个分支的叶子节点 * len = 1，说明当前递归正在遍历某分支的叶子节点 */ if(len==0) return null; TreeNode root = new TreeNode(postorder[p_start+len-1]); if(len==1) return root;
 /** * 2. 计算某个分支的左子节点的个数，or 左子节点的长度 * 这里L从0开始，在前序遍历中，根先被遍历因此 L=1，而中序遍历左子节点先被遍历因此 L初始化为0 */ int L = 0; for(;L<len;++L){ if(inorder[i_start+L]==postorder[p_start+len-1]){ break; } } /** * 3. 采用分治的思想，分别找到root节点的左子节点和右子节点 * i_start 记录中序数组的起始点 * p_start 记录后序数组的起始点 * L是当前分支的左子节点的个数 * len是当前数组的长度 */ root.left = makeTree(inorder,postorder,i_start,p_start,L); root.right = makeTree(inorder,postorder,i_start+L+1,p_start+L,len-L-1); //4. 返回root节点 return root; }}

class Solution {
 private Map<Integer,Integer> map = new HashMap<Integer,Integer>();
 public TreeNode buildTree(int[] inorder, int[] postorder) { for(int i=0;i<inorder.length;i++){ map.put(inorder[i],i); }
 return makeTree(inorder, postorder, 0, 0, postorder.length, map); }
 public TreeNode makeTree(int[] inorder, int[] postorder,int i_start,int p_start,int len,Map<Integer,Integer> map){ /** * 1. 递归终止条件 * len = 0，说明上次递归已经遍历到了某个分支的叶子节点 * len = 1，说明当前递归正在遍历某分支的叶子节点 */ if(len==0) return null; TreeNode root = new TreeNode(postorder[p_start+len-1]); if(len==1) return root;
 /** * 2. 计算某个分支的左子节点的个数，or 左子节点的长度 * 这里L从0开始，在前序遍历中，根先被遍历因此 L=1，而中序遍历左子节点先被遍历因此 L初始化为0 */ int L = map.get(root.val)-i_start; /** * 3. 采用分治的思想，分别找到root节点的左子节点和右子节点 * i_start 记录中序数组的起始点 * p_start 记录后序数组的起始点 * L是当前分支的左子节点的个数 * len是当前数组的长度 */ root.left = makeTree(inorder, postorder, i_start, p_start, L, map); root.right = makeTree(inorder, postorder, i_start+L+1, p_start+L, len-L-1, map); //4. 返回root节点 return root; }}

class Solution {
 public static boolean isSameTree(TreeNode p, TreeNode q) { //1. 递归终止条件，如果当前p、q 同时为空，则说明遍历完了两颗二叉树，所以相同返回true if(p==null && q==null) return true;
 //2. 判断当前 p、q 节点是否同时不为空，是则继续判断是否相同，相同则递归判断其左右子节点 else if(p != null && q != null){ if(p.val==q.val) //有一个不相同则两棵树就不相同，所以用与运算 return isSameTree(p.left,q.left) && isSameTree(p.right, q.right); }
 /** * 3. 其他情况则说明两棵树不相同，比如有某棵树的p or q 节点，一个为null，一个不为null * 或则两个节点都不为空，但是不相同，也需要直接返回false */ return false; }}