hot100-二叉树

二叉树

二叉树递归

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

java">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;}
}

二叉树迭代

前序遍历

迭代法

java">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;
}

中序遍历

迭代法

java">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的类，优点是只需要更改顺序就可以使三个顺序都能写

java">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，则断联，记录，进入右子树。

java">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;}
}

后序遍历

反转法

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

java">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;}

访问标记法（染色法）

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

java">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 遍历法通过在遍历过程中使用指针而避免了使用栈或递归，从而节省空间。

java">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. 二叉树的最大深度

解法一、递归

java">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. 翻转二叉树

解法一、递归

java">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. 对称二叉树

解法一、递归

java">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的情况下构建新节点，总之就是改换边界条件

java">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. 二叉树的直径

解法一、递归

java">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. 二叉树的层序遍历

解法一层序遍历

java">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. 将有序数组转换为二叉搜索树

解法一、递归

java">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. 验证二叉搜索树

解法一、递归

java">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

java">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的关系剪枝，可以效率提升一半多。

java">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是剪枝，第三个是答案赋值判断

java">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. 二叉树的右视图

解法一、递归

java">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;}
}