hot100-二叉树

二叉树

二叉树递归

相当于这个的顺序来回调换

class Solution {private List<Integer> res = new ArrayList<>();public List<Integer> inorderTraversal(TreeNode root) {if(root == null)return res;inorderTraversal(root.left);res.add(root.val);inorderTraversal(root.right);return res;}
}

二叉树迭代

前序遍历

迭代法

public List<Integer> preOrderTraversal(TreeNode root) {List<Integer> res = new ArrayList<Integer>();if (root == null) {return res;}Deque<TreeNode> stack = new LinkedList<TreeNode>();TreeNode node = root;while (!stack.isEmpty() || node != null) {while (node != null) {res.add(node.val);stack.push(node);node = node.left;}node = stack.pop();node = node.right;}return res;
}

中序遍历

迭代法

public List<Integer> preOrderTraversal(TreeNode root) {List<Integer> res = new ArrayList<Integer>();if (root == null) {return res;}Deque<TreeNode> stack = new LinkedList<TreeNode>();TreeNode node = root;while (!stack.isEmpty() || node != null) {while (node != null) {stack.push(node);node = node.left;}node = stack.pop();res.add(node.val);node = node.right;}return res;
}

染色法

缺点是要写一个pair的类，优点是只需要更改顺序就可以使三个顺序都能写

class Pair<K, V> {private K key;private V value;public Pair(K key, V value) {this.key = key;this.value = value;}public K getKey() {return key;}public V getValue() {return value;}
}class Solution {public List<Integer> inorderTraversal(TreeNode root) {List<Integer> res = new LinkedList<>();Deque<Pair<Integer, TreeNode>> stack = new ArrayDeque<>();stack.push(new Pair<>(0,root));while(!stack.isEmpty()){Pair<Integer,TreeNode> newPair = stack.pop();int color = newPair.getKey();TreeNode node = newPair.getValue();if(node == null)continue;if(color == 0){stack.push(new Pair<>(0,node.right));stack.push(new Pair<>(1,node));stack.push(new Pair<>(0,node.left));}else{res.add(node.val);}}return res;}
}

Morris法

①第一个循环：是否为空

②判断左子树是否为空，是则记录+进入右子树，不是则进入左子树

③如果最右的最右为空，则链接，进入左子树。如果最右的最右为root，则断联，记录，进入右子树。

class Solution {public List<Integer> inorderTraversal(TreeNode root) {List<Integer> res = new LinkedList<>();while(root !=null){if(root.left == null){res.add(root.val);root = root.right;}else{//有左子树的情况TreeNode pre = root.left;while(pre.right != null && pre.right != root){pre = pre.right;}if(pre.right == null){pre.right = root;root = root.left;}else{pre.right = null;//断开res.add(root.val);root = root.right;}}}return res;}
}

后序遍历

反转法

其实就是将递归暗处的栈变成明面

public class PostorderTraversal {public List<Integer> postorderTraversal(TreeNode root) {List<Integer> result = new ArrayList<>();if (root == null) return result;Stack<TreeNode> stack = new Stack<>();Stack<Integer> output = new Stack<>();stack.push(root);while (!stack.isEmpty()) {TreeNode node = stack.pop();output.push(node.val);if (node.left != null) stack.push(node.left);if (node.right != null) stack.push(node.right);}while (!output.isEmpty()) {result.add(output.pop());}return result;}

访问标记法（染色法）

（使用额外的标记来指示节点是否已经访问）

public class PostorderTraversal {public List<Integer> postorderTraversal(TreeNode root) {List<Integer> result = new ArrayList<>();if (root == null) return result;Stack<TreeNode> stack = new Stack<>();TreeNode prev = null;while (!stack.isEmpty() || root != null) {while (root != null) {stack.push(root);root = root.left;}root = stack.peek();if (root.right == null || root.right == prev) {result.add(root.val);stack.pop();prev = root;root = null; // We have finished this node} else {root = root.right; // Move to the right child}}return result;}

Morris法（线性时间，常数空间）

Morris 遍历法通过在遍历过程中使用指针而避免了使用栈或递归，从而节省空间。

public List<Integer> postorderTraversal(TreeNode root) {List<Integer> result = new ArrayList<>();if (root == null) return result;TreeNode dummy = new TreeNode(0);dummy.left = root;TreeNode curr = dummy;while (curr != null) {if (curr.left == null) {curr = curr.right;} else {TreeNode prev = curr.left;while (prev.right != null && prev.right != curr) {prev = prev.right;}if (prev.right == null) {prev.right = curr;curr = curr.left;} else {reverse(curr.left, prev);TreeNode temp = prev;while (temp != null) {result.add(temp.val);temp = temp.right;}reverse(prev, curr.left);prev.right = null;curr = curr.right;}}}return result;}private void reverse(TreeNode from, TreeNode to) {if (from == to) return;TreeNode x = from, y = from.right;while (x != to) {x.right = y.right;y.right = x;x = y;y = y.right;}}

104. 二叉树的最大深度

解法一、递归 

class Solution {public int maxDepth(TreeNode root) {if(root == null)return 0;int leftMax = maxDepth(root.left);int rightMax = maxDepth(root.right);return Math.max(leftMax,rightMax) + 1;}
}

226. 翻转二叉树

解法一、递归

class Solution {public TreeNode invertTree(TreeNode root) {if(root == null)return root;invertTree(root.left);invertTree(root.right);TreeNode tmp = root.left;root.left = root.right;root.right = tmp;return root;}
}

101. 对称二叉树

解法一、递归

class Solution {public boolean isSymmetric(TreeNode root) {return isS(root.left,root.right);}private boolean isS(TreeNode left,TreeNode right){if(left == null || right == null)return left == right;return left.val == right.val && isS(left.left,right.right)&&isS(left.right,right.left);}
}

解法二、迭代 

因为List情况下不能add null，所以改换成Queue。不过不改也可以，只需要在null的情况下构建新节点，总之就是改换边界条件

class Solution {public boolean isSymmetric(TreeNode root) {return isS(root,root);}private boolean isS(TreeNode left,TreeNode right){Queue<TreeNode> res = new LinkedList<>();res.add(left);res.add(right);while (!res.isEmpty()){TreeNode u = res.poll();TreeNode v = res.poll();if (u == null && v == null) {continue;}if ((u == null || v == null) || (u.val != v.val)) {return false;}res.offer(u.left);res.offer(v.right);res.offer(u.right);res.offer(v.left);}return true;}
}

543. 二叉树的直径

解法一、递归

class Solution {private int res = 0;public int diameterOfBinaryTree(TreeNode root) {dfs(root);return res;}private  int dfs(TreeNode root){if(root == null)return -1;int l = dfs(root.left)+1;int r = dfs(root.right)+1;res = Math.max(res,l+r);return Math.max(l,r);}
}

 
102. 二叉树的层序遍历

解法一 层序遍历

class Solution {public List<List<Integer>> levelOrder(TreeNode root) {Queue<TreeNode> q = new LinkedList<>();List<List<Integer>> res = new LinkedList<>();q.offer(root);while(!q.isEmpty()){Queue<TreeNode> p = q;q = new LinkedList<>();List<Integer> tmp = new LinkedList<>();while(!p.isEmpty()){TreeNode node = p.poll();if(node == null)continue;q.add(node.left);q.add(node.right);tmp.add(node.val);}if(!tmp.isEmpty())res.add(tmp);}return res;}
}

108. 将有序数组转换为二叉搜索树

解法一、递归

class Solution {public TreeNode sortedArrayToBST(int[] nums) {int n = nums.length,mid = n/2;return create(nums,0,n);}private TreeNode create(int[] nums,int x,int y){if(x==y)return null;int mid = x + (y-x)/2;TreeNode node = new TreeNode(nums[mid]);node.left = create(nums,x,mid);node.right = create(nums,mid+1,y);return node;}
}

98. 验证二叉搜索树

解法一、递归

class Solution {public boolean isValidBST(TreeNode root) {if(root == null)return true;return BST(root.left,Long.MIN_VALUE,root.val) && BST(root.right,root.val,Long.MAX_VALUE);}public boolean BST(TreeNode root,long x,long y) {if(root == null)return true;if(root.val <= x || root.val >= y )return false;return BST(root.left,x,root.val) && BST(root.right,root.val,y);}
}

 解法二、中序递增

中序出来的数组一定是递增的，同时，递增数组中序构建也一定是BST

class Solution {public boolean isValidBST(TreeNode root) {List<Integer> tmp = new LinkedList<>();while(root != null){if(root.left == null){tmp.add(root.val);root = root.right;}else{TreeNode node = root.left;while(node.right != null && node.right != root){node = node.right;}if(node.right == null){node.right = root;root = root.left;}else{node.right = null;tmp.add(root.val);root = root.right;}}}int n = tmp.size(),num = tmp.get(0);for(int i = 1;i < n;i++){if(tmp.get(i) <= num)return false;num = tmp.get(i);}return true;}
}

230. 二叉搜索树中第 K 小的元素

解法一、中序递增

98的变式。在while里判断一下tmp.size()和k的关系剪枝，可以效率提升一半多。

class Solution {public int kthSmallest(TreeNode root, int k) {List<Integer> tmp = new LinkedList<>();while(root != null){if(root.left == null){tmp.add(root.val);root = root.right;}else{TreeNode node = new TreeNode();while(node.right != null && node.right != root){node = node.right;}if(node.right == null){node.right = root;}else{node.right = null;tmp.add(root.val);root = root.right;}}}return tmp.get(k);}
}

 解法二、dfs

第一个if是边界，第二个if是剪枝，第三个是答案赋值判断

class Solution {private int k,res= 0;public int kthSmallest(TreeNode root, int k) {this.k = k;dfs(root);return res;}private void dfs(TreeNode root){if(root==null)return;dfs(root.left);if(k==0)return;if(--k==0)res = root.val;dfs(root.right);}
}

199. 二叉树的右视图

解法一、递归

class Solution {public List<Integer> rightSideView(TreeNode root) {Deque<TreeNode> a = new LinkedList<>();a.add(root);List<Integer> res = new LinkedList<>();if(root == null)return res;while(!a.isEmpty()){Deque<TreeNode> q = a;a = new LinkedList<>();res.add(q.getLast().val);while(!q.isEmpty()){TreeNode node = q.pollLast();if(node.right != null)a.addFirst(node.right);if(node.left != null)a.addFirst(node.left);}}return res;}
}

105. 从前序与中序遍历序列构造二叉树

 

解法一、递归

靠前序确定节点 靠中序确定左右树 从顶至下递归进行

两个改进：①搜索改进，甚至使用哈希表O（1）。②更改函数传入，l和r，避免复制数组的开销

class Solution {public TreeNode buildTree(int[] preorder, int[] inorder) {int n = preorder.length;if(n==0)return null;int index = findNum(inorder,preorder[0]);int [] l = Arrays.copyOfRange(inorder,0,index);int [] r = Arrays.copyOfRange(inorder,index+1,n);int [] pre1 = Arrays.copyOfRange(preorder,1,1+index);int [] pre2 = Arrays.copyOfRange(preorder,1+index,n);TreeNode left = buildTree(pre1,l);TreeNode right = buildTree(pre2,r);return new TreeNode(preorder[0],left,right);}public int findNum(int[] nums,int num){int n = nums.length;for(int i = 0;i < n;i++){if(nums[i] == num)return i;}return -1;}
}

437. 路径总和 III

解法一、 递归 哈希

务必恢复现场

class Solution {private int ans;public int pathSum(TreeNode root, int targetSum) {Map<Long,Integer>cnt = new HashMap<>();cnt.put(0L,1);dfs(root,0,targetSum,cnt);return ans;}private void dfs(TreeNode root,long s,int targetSum,Map<Long,Integer> cnt){if(root == null)return;s+= root.val;ans += cnt.getOrDefault(s - targetSum, 0);cnt.merge(s,1,Integer::sum);dfs(root.left,s,targetSum,cnt);dfs(root.right,s,targetSum,cnt);cnt.merge(s,-1,Integer::sum);}
}

236. 二叉树的最近公共祖先

解法一、递归找路径，判断两条路径共同开头

你根本无法理解这个到底有多慢jpg

class Solution {public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {List<TreeNode> l = new LinkedList<>();List<TreeNode> r = new LinkedList<>();dfs(root,p,l);dfs(root,q,r);int n = l.size(),m = r.size(),x = 0,y = 0;while(x < n && y < m && l.get(x) == r.get(y)){x++;y++;}TreeNode res;if(x>=n)res = l.get(n-1);else if(y>=m)res = r.get(m-1);else res = l.get(x-1);return res;}public boolean dfs(TreeNode root,TreeNode p,List<TreeNode> list){if(root == null)return false;list.add(root);if(root == p){return true;}//都是错的才removeif(dfs(root.left,p,list) || dfs(root.right,p,list))return true;list.remove(list.size()-1);return false;}
}

 解法二、递归

进行了一个很大的剪枝。都=null即都没查到，两个都非null即当前节点就公共，p在q下面则返回q即可。

class Solution {public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {if(root == null || root == p || root == q)return root;TreeNode left = lowestCommonAncestor(root.left,p,q);TreeNode right = lowestCommonAncestor(root.right,p,q);if(left != null && right != null)return root;return left != null ? left : right;}}

124. 二叉树中的最大路径和​​​​​​​

解法一、递归

class Solution {private int res = Integer.MIN_VALUE;public int maxPathSum(TreeNode root) {dfs(root);return res;}private int dfs(TreeNode root){if(root == null)return 0;int left = dfs(root.left);int right = dfs(root.right);res = Math.max(left+right+root.val,res);return Math.max(0,Math.max(left+root.val,right+root.val));} 
}