二叉树

二叉树的特性天然就需要使用递归来解决。

104. 二叉树的最大深度

• 该问题的边界条件是：空节点。
• 计算机是怎么执行递归的？
  • 当程序执行“递”动作时，计算机使用栈保存这个发出“递”动作的对象，程序不断“递”，计算机不断压栈，直到边界时，程序发生“归”动作，正好将执行的答案“归”给栈顶元素，随后程序不断“归”，计算机不断出栈，直到返回原问题的答案，栈空。

	public int maxDepth(TreeNode root) {if (root == null) {return 0;}int maxLeft = maxDepth(root.left);int maxRight = maxDepth(root.right);return Math.max(maxLeft, maxRight) + 1;}

100.相同的树

public boolean isSameTree(TreeNode p, TreeNode q) {if (p == null && q == null) {return true;}if (p == null && q!= null) {return false;}if (p != null && q == null) {return false;}if (q.val != p.val) {return false;}return isSameTree(p.left, q.left) && isSameTree(p.right, q.right);}

101.对称二叉树

public boolean isSymmetric(TreeNode root) {if (root == null)return true;return isSameTree(root.left, root.right);}public boolean isSameTree(TreeNode p, TreeNode q) {if (p == null && q == null) {return true;}if (p == null && q!= null) {return false;}if (p != null && q == null) {return false;}if (q.val != p.val) {return false;}return isSameTree(p.left, q.right) && isSameTree(p.right, q.left);}

110. 平衡二叉树

此问题可以拆解成：当前节点是否平衡 && 节点的左子树是否平衡 && 节点的右子树书否平衡

	public boolean isBalanced(TreeNode root) {if (root == null) {return true;}return Math.abs(getHight(root.left) - getHight(root.right)) <= 1 && isBalanced(root.left) && isBalanced(root.right);}private int getHight(TreeNode root) {if (root == null) {return 0;}return Math.max(getHight(root.left), getHight(root.right)) + 1;}

• 提前返回结果

	public boolean isBalanced(TreeNode root) {if (root == null) {return true;}return getHight(root) != -1;}private int getHight(TreeNode root) {if (root == null) {return 0;}int leftHight = getHight(root.left);if (leftHight == -1) {return -1;}int rightHight = getHight(root.right);if (rightHight == -1 || Math.abs(leftHight - rightHight) > 1) {return -1;}return Math.max(leftHight, rightHight) + 1;}

199. 二叉树的右视图

• DFS解法

	public List<Integer> rightSideView(TreeNode root) {List<Integer> ans = new ArrayList<>();f(root, 0, ans);return ans;}private void f(TreeNode root, int high, List<Integer> ans) {if (root == null) {return;}// 每次记录和树高相同的节点，因为左视图就可以从左子树开始，右视图就从右子树开始就好了if (high == ans.size()){ans.add(root.val);}f(root.right, high + 1, ans);f(root.left, high + 1, ans);}

• BFS， 使用队列

public List<Integer> rightSideView(TreeNode root) {List<Integer> ans = new ArrayList<>();Queue<TreeNode> queue = new ArrayDeque<>();if (root == null) {return ans;}queue.add(root);while (!queue.isEmpty()) {int size = queue.size();for (int i = 0; i < size; i++) {TreeNode node = queue.poll();if (i == 0) {ans.add(node.val);}if (node.right != null) {queue.add(node.right);}if (node.left != null) {queue.add(node.left);}}}return ans;}

树的遍历

144.前序遍历

    private void preOrderTraverse(TreeNode root) {if (root != null) {System.out.print(root.val + " ");preOrderTraverse(root.left);preOrderTraverse(root.right);}}

public List<Integer> preorderTraversal(TreeNode root) {List<Integer> ans = new ArrayList<>();if (root == null) {return ans;}LinkedList<TreeNode> stack = new LinkedList<>();// 初始化栈stack.push(root);while (!stack.isEmpty()) {TreeNode node = stack.pop();// 前序遍历，优先访问根节点。然后访问左子树，最后访问右子树ans.add(node.val);// 先访问左子树，那右子树可以先入栈后访问if (node.right != null) {stack.push(node.right);}// 左子树先访问，因此后入栈先访问if (node.left != null) {stack.push(node.left);}}return ans;}

    public List<Integer> preorderTraversal1(TreeNode root) {List<Integer> ans = new ArrayList<>();if (root == null) {return ans;}LinkedList<TreeNode> stack = new LinkedList<>();TreeNode cur = root;while (cur != null || !stack.isEmpty()) {if (cur != null) {ans.add(cur.val);stack.push(cur);cur = cur.left;} else {cur = stack.pop();cur = cur.right;}}return ans;}

94.中序遍历

    private void inOrderTraverse(TreeNode root) {if (root != null) {preOrderTraverse(root.left);System.out.print(root.val + " ");preOrderTraverse(root.right);}}

public List<Integer> inorderTraversal(TreeNode root) {List<Integer> ans = new ArrayList<>();if (root == null) {return ans;}LinkedList<TreeNode> stack = new LinkedList<>();TreeNode cur = root;while (cur != null || !stack.isEmpty()) {if (cur != null) {stack.push(cur);cur = cur.left;} else {cur = stack.pop();ans.add(cur.val);cur = cur.right;}}return ans;}

145.后序遍历

    private void postOrderTraverse(TreeNode root) {if (root != null) {preOrderTraverse(root.left);preOrderTraverse(root.right);System.out.print(root.val + " ");}}

当访问完一棵子树的时候，我们用prev指向该节点。
这样，在回溯到父节点的时候，我们可以依据prev是指向左子节点，还是右子节点，来判断父节点的访问情况。

	List<Integer> ans = new LinkedList<>();Stack<TreeNode> stack = new Stack<>();TreeNode prev = null;//主要思想：//由于在某颗子树访问完成以后，接着就要回溯到其父节点去//因此可以用prev来记录访问历史，在回溯到父节点时，可以由此来判断，上一个访问的节点是否为右子树while (root != null || !stack.isEmpty()) {// 左子树全部入栈if (root != null) {stack.push(root);root = root.left;} else {//从栈中弹出的元素，左子树一定是访问完了的root = stack.pop();//判断右子树是否是最后一个，或者已经访问过了。//满足上面条件就说明可以加入结果集了if (root.right == null || prev == root.right) {ans.add(root.val);//更新历史访问记录，这样回溯的时候父节点可以由此判断右子树是否访问完成prev = root;root = null;} else {//如果右子树没有被访问，那么将当前节点压栈，知道该节点的最后一个右子树//右子树全部压栈stack.push(root);root = root.right;}}}return ans;

102. 层序遍历

    public void levelTraverse(TreeNode root) {if (root == null) {return;}LinkedList<TreeNode> queue = new LinkedList<>();queue.offer(root);while (!queue.isEmpty()) {TreeNode node = queue.poll();System.out.print(node.val+"  ");if (node.left != null) {queue.offer(node.left);}if (node.right != null) {queue.offer(node.right);}}}

102. 深度遍历

    public void depthOrderTraverse(TreeNode root) {if (root == null) {return;}LinkedList<TreeNode> stack = new LinkedList<>();stack.push(root);while (!stack.isEmpty()) {TreeNode node = stack.pop();System.out.print(node.val+"  ");if (node.right != null) {stack.push(node.right);}if (node.left != null) {stack.push(node.left);}}}

98. 验证搜索二叉树

• 前序遍历
  注意，Java最大值有边界值，不像python有无穷大的概念

    public boolean isValidBST(TreeNode root) {return isValidBST(root, Long.MIN_VALUE, Long.MAX_VALUE);}private boolean isValidBST(TreeNode node, long left, long right) {if (node == null) {return true;}long x = node.val;return left < x && x < right && isValidBST(node.left, left, x) &&isValidBST(node.right, x, right);}

• 中序遍历

class Solution {private long pre = Long.MIN_VALUE;public boolean isValidBST(TreeNode root) {if (root == null) {return true;}// 左子树不是搜索二叉树if (!isValidBST(root.left)) {return false;}// 中序遍历先遍历左子树，然后根节点，最后右子树。这里只能判断否，不能判断trueif (root.val <= pre) {return false;}pre = root.val;// 右子树是否为搜索二叉树return isValidBST(root.right);}
}

• 后序遍历

	public boolean isValidBST(TreeNode root) {return dfs(root)[1] != Long.MAX_VALUE;}private long[] dfs(TreeNode node) {if (node == null) {return new long[]{Long.MAX_VALUE, Long.MIN_VALUE};}long[] left = dfs(node.left);long[] right = dfs(node.right);long x = node.val;// 也可以在递归完左子树之后立刻判断，如果发现不是二叉搜索树，就不用递归右子树了if (x <= left[1] || x >= right[0]) {return new long[]{Long.MIN_VALUE, Long.MAX_VALUE};}return new long[]{Math.min(left[0], x), Math.max(right[1], x)};}

111. 二叉树的最小深度

• 层次遍历

		public int minDepth(TreeNode root) {if (root == null){return 0;}int ans = 0;LinkedList<TreeNode> queue = new LinkedList<TreeNode>();// 层次遍历只要根节点就可以返回queue.add(root);while(!queue.isEmpty()) {ans++;int size  = queue.size();while(size > 0){TreeNode node = queue.poll();size--;if (node.left == null && node.right == null){// 遇到根节点了return ans;}if (node.left != null){queue.add(node.left);}if (node.right != null){queue.add(node.right);}}}return ans;}

• 递归
  • 那么这样写为什么不对呢

	public int minDepth(TreeNode root) {if(root==null) return 0;if (root.left == null && root.right == null) {return 1;}int left=minDepth(root.left);int right=minDepth(root.right);return Math.min(left,right)+1;}

叶子节点的定义是对的，但是树的高度没有定义对。
比如：这样的树的高度定义是2，而不是1。
树的高度定义为：

• 若左子树为空，那么高度就等于右子树高度+1

• 若右子树为空，那么高度就等有左子树高度+1

• 若左右子树都为空，那么高度就为1.
  

• 自底向上: 树的最大高度这样写也没有问题
  定义 minDepth(root) 表示以节点 root 为根的树的最小深度。

分类讨论：

• 如果 node 是空节点，由于没有节点，返回 0。
• 如果 node 没有右儿子，那么深度就是左子树的深度加一，即 dfs(node)=dfs(node.left)+1。
• 如果 node 没有左儿子，那么深度就是右子树的深度加一，即 dfs(node)=dfs(node.right)+1。
• 如果 node 左右儿子都有，那么分别递归计算左子树的深度，以及右子树的深度，二者取最小值再加一，即

class Solution {public int minDepth(TreeNode root) {// 空节点就没有高度，返回0if(root==null) return 0;// 左右子树都为空，则只有根节点，返回高度1if (root.left == null && root.right == null) {return 1;}// 若左子树为空if (root.left == null) {return minDepth(root.right) + 1;}// 若右子树为空if (root.right == null) {return minDepth(root.left) + 1;}// 若左右子树都不为空，返回左右子树高度的最小值 在+1。 （＋1是因为当前节点，返回+1后就是当前节点的高度了）。子树的高度+1 = 当前高度return Math.min(minDepth(root.left), minDepth(root.right)) + 1;}
}

112. 路径之和

public boolean hasPathSum(TreeNode root, int targetSum) {if (root == null) {return false;}targetSum -= root.val;// root是叶子节点if (root.left == root.right) {return targetSum == 0;}return hasPathSum(root.left, targetSum) || hasPathSum(root.right, targetSum);}

129. 求根节点的到叶子节点数字之和

class Solution {private int sum = 0;public int sumNumbers(TreeNode root) {dfs(root, 0);return sum;}public void dfs(TreeNode node, int currVal) {if (node == null) {return;}currVal = currVal * 10 + node.val;if (node.left == node.right) {sum += currVal;return;}dfs(node.left, currVal);dfs(node.right, currVal);}
}

1448. 统计二叉树中好节点的数目

class Solution {private int ans = 0;public int goodNodes(TreeNode root) {if (root == null) {return 0;}dfs(root, root.val);return ans;}private void dfs(TreeNode node, int max) {if (node == null) {return;}int x = max;if (node.val >= max) {ans ++;x = node.val;}dfs(node.left, x);dfs(node.right, x);}
}

987. 二叉树的垂序遍历

class Solution {private Map<Integer, List<Integer>> map = new HashMap<>();public List<List<Integer>> verticalTraversal(TreeNode root) {Map<Integer, List<int[]>> groups = new TreeMap<>();dfs(root, 0, 0, groups);List<List<Integer>> ans = new ArrayList<>(groups.size());// 当前col Key下的元素排序，value: List<int[]> 是一个Listfor (List<int[]> g: groups.values()) {// 先高排序，在层次上面的优先加入，对于层次一样的，按照值排序g.sort((a,b) -> a[0] != b[0] ? a[0]- b[0] : a[1] - b[1]);List<Integer> vals = new ArrayList<>(g.size());for (int[] p : g) {vals.add(p[1]);}ans.add(vals);}return ans;}private void dfs(TreeNode node, int row, int col, Map<Integer, List<int[]>> groups) {if (node == null) {return;}groups.computeIfAbsent(col, k -> new ArrayList<>()).add(new int[]{row, node.val});dfs(node.left, row + 1, col -1, groups);dfs(node.right, row + 1, col + 1, groups);}
}

• 直接使用三元组

class Solution {public List<List<Integer>> verticalTraversal(TreeNode root) {List<int[]> data = new ArrayList<>();dfs(root, 0, 0, data);List<List<Integer>> ans = new ArrayList<>();data.sort((a, b) -> a[0] != b[0] ? a[0] - b[0] : a[1] != b[1] ? a[1] - b[1] : a[2] - b[2]);int lastCol = Integer.MIN_VALUE;for (int[] d : data) {// 为什么这样写： 统一垂序的位置放在一起if (d[0] != lastCol) {lastCol = d[0];ans.add(new ArrayList<>());}ans.get(ans.size() - 1).add(d[2]);}return ans;}private void dfs(TreeNode node, int row, int col, List<int[]> data) {if (node == null) {return;}data.add(new int[]{col, row, node.val});dfs(node.left, row + 1, col - 1, data);dfs(node.right, row + 1, col + 1, data);}
}

226. 翻转二叉树

 	public TreeNode invertTree(TreeNode root) {if (root == null) {return null;}// 需要记录当前节点的左右子树TreeNode left = root.left;TreeNode right = root.right;root.left = invertTree(right);root.right = invertTree(left);return root;}

617. 合并二叉树

 public TreeNode mergeTrees(TreeNode root1, TreeNode root2) {// 为空，返回另一个二叉树if (root1 == null) {return root2;}if (root2 == null) {return root1;}root1.val += root2.val;root1.left = mergeTrees(root1.left, root2.left);root1.right = mergeTrees(root1.right, root2.right);return root1;}

1026. 节点与其祖先的最大差值

class Solution {private int ans = 0;public int maxAncestorDiff(TreeNode root) {if (root == null) {return 0;}dfs(root, root.val, root.val);return ans;}private void dfs(TreeNode node, int min, int max) {if (node == null) {return;}if (node.val > max) {ans = Math.max(ans, node.val - min);max = node.val;}if (node.val < min) {ans = Math.max(ans, max - node.val);min = node.val;}dfs(node.left, min, max);dfs(node.right, min, max);}
}

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

class Solution {public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {//当前节点是null 或者 当前节点是p 或者当前节点是qif (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;}// 只有左子树找到if (left != null) {return left;}// 只有右子树找到，或者都找不到。return right;}
}

[235. 二叉搜索树的最近公共祖先]

class Solution {public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {if (root == null) {return null;}int x = root.val;if (p.val < x && q.val < x){return lowestCommonAncestor(root.left, p,q);}if(p.val > x && q.val > x) {return lowestCommonAncestor(root.right, p, q);}return root;}
}

103. 二叉树的锯齿形层次遍历

class Solution {public List<List<Integer>> zigzagLevelOrder(TreeNode root) {List<List<Integer>> ans = new ArrayList<>();if (root == null) {return ans;}LinkedList<TreeNode> queue = new LinkedList<>();queue.add(root);boolean even  = false;while(!queue.isEmpty()){int size = queue.size();List<Integer> list = new ArrayList<>();while(size > 0) {TreeNode node = queue.poll();list.add(node.val);if (node.left != null) {queue.add(node.left);}if (node.right != null) {queue.add(node.right);}size--;}if (even) {Collections.reverse(list);}even = !even;ans.add(list);}return ans;}
}

513. 找树左下角的值

class Solution {public int findBottomLeftValue(TreeNode root) {int x = root.val;LinkedList<TreeNode> queue = new LinkedList<>();queue.add(root);while(!queue.isEmpty()) {TreeNode node = queue.poll();x = node.val;if (node.right != null) {queue.add(node.right);}if (node.left != null) {queue.add(node.left);}}return x;}
}

107. 二叉树的层次遍历II

class Solution {public List<List<Integer>> levelOrderBottom(TreeNode root) {List<List<Integer>> ans = new ArrayList<>();if (root == null) {return ans;}LinkedList<TreeNode> queue = new LinkedList<>();queue.add(root);while(!queue.isEmpty()){int size = queue.size();List<Integer> list = new ArrayList<>();while(size > 0) {TreeNode node = queue.poll();list.add(node.val);if (node.left != null) {queue.add(node.left);}if (node.right != null) {queue.add(node.right);}size--;}ans.add(list);}Collections.reverse(ans);return ans;}
}

116. 填充每个节点的下一个右侧节点指针 同117. 填充每个节点的下一个右侧节点指针II

class Solution {public Node connect(Node root) {if (root == null) {return root;}LinkedList<Node> queue = new LinkedList<>();queue.offer(root);while (!queue.isEmpty()) {int size = queue.size();Node node = null;while (size > 0) {node = queue.poll();node.next = queue.peek();if (node.left != null) {queue.offer(node.left);}if (node.right != null) {queue.offer(node.right);}size --; }node.next = null;}return root;}
}

回溯

17. 电话号码的字母组合

class Solution {private String[] MAPPING = new String[]{"","","abc","def","ghi","jkl","mno","pqrs","tuv","wxyz"};private List<String> ans = new ArrayList<String>();private char[] digitsCharArray;private char[] path;public List<String> letterCombinations(String digits) {int n  = digits.length();if (n == 0) {return List.of();}this.digitsCharArray = digits.toCharArray();this.path = new char[n];dfs(0);return ans;}private void dfs(int index) {if (index == digitsCharArray.length) {ans.add(new String(path));return;}for (char c : MAPPING[digitsCharArray[index] - '0'].toCharArray()) {path[index] = c;dfs(index + 1);}}}

子集型回溯

• 每个元素都可以选或者不选
• 回溯三问
  • 当前操作？枚举第i个数选/不选
  • 子问题？从下标≥i的数字中构造子集
  • 下一个子问题？从下标≥i + 1的数字中构造子集

78. 子集

class Solution {private List<List<Integer>> ans = new ArrayList<>();private ArrayList<Integer> path = new ArrayList<>();private int[] nums;public List<List<Integer>> subsets(int[] nums) {this.nums = nums;dfs(0);return ans;}private void dfs(int index) {System.out.println("index:" + index + "  path: " + this.path);if (index == this.nums.length){System.out.println("添加进ans: " + String.valueOf(this.path));ans.add(new ArrayList<>(this.path));return;}path.add(this.nums[index]);System.out.println("添加进path: " + String.valueOf(this.path));dfs(index + 1);System.out.println("移除path中: " + String.valueOf(this.path.get(this.path.size() - 1)));path.remove(this.path.size() - 1);System.out.println("移除后path: " + String.valueOf(this.path));dfs(index + 1);}
}

		index:0  path: []添加进path: [1]index:1  path: [1]添加进path: [1, 2]index:2  path: [1, 2]添加进path: [1, 2, 3]index:3  path: [1, 2, 3]添加进ans: [1, 2, 3]移除path中: 3移除后path: [1, 2]index:3  path: [1, 2]添加进ans: [1, 2]移除path中: 2移除后path: [1]index:2  path: [1]添加进path: [1, 3]index:3  path: [1, 3]添加进ans: [1, 3]移除path中: 3移除后path: [1]index:3  path: [1]添加进ans: [1]移除path中: 1移除后path: []index:1  path: []添加进path: [2]index:2  path: [2]添加进path: [2, 3]index:3  path: [2, 3]添加进ans: [2, 3]移除path中: 3移除后path: [2]index:3  path: [2]添加进ans: [2]移除path中: 2移除后path: []index:2  path: []添加进path: [3]index:3  path: [3]添加进ans: [3]移除path中: 3移除后path: []index:3  path: []添加进ans: []

• [1,2] 和[2, 1] 是重复的子集

• 为了避免重复

• 下一个数应该大于当前选择的数

• 回溯三问：

  • 当前操作？枚举一个下标j ≥ i的数字，加入path
  • 子问题？ 从下标≥ i的数字中构造子集
  • 下一个子问题？ 从下标 ≥ j + 1 的数字中构造子集

class Solution {private List<List<Integer>> ans = new ArrayList<>();private ArrayList<Integer> path = new ArrayList<>();private int[] nums;public List<List<Integer>> subsets(int[] nums) {this.nums = nums;dfs2(0);return ans;}private void dfs2(int index) {System.out.println("index:" + index + "  path: " + this.path);// 递归到每一个节点都可能是答案ans.add(new ArrayList<>(this.path));System.out.println("添加进ans: " + String.valueOf(this.path));if (index == this.nums.length){return;}System.out.println("========================index:" + index);// 枚举每一种可能性for (int j = index; j < this.nums.length; j++) {System.out.println("j:" + j);this.path.add(this.nums[j]);System.out.println("添加进path: " + String.valueOf(this.path));dfs2(j + 1);System.out.println("移除path中: " + String.valueOf(this.path.get(this.path.size() - 1)));path.remove(this.path.size() - 1);System.out.println("移除后path: " + String.valueOf(this.path));}System.out.println("========================index" + index + "结束");}
}

• 输出

		index:0  path: []添加进ans: []========================index:0j:0添加进path: [1]index:1  path: [1]添加进ans: [1]========================index:1j:1添加进path: [1, 2]index:2  path: [1, 2]添加进ans: [1, 2]========================index:2j:2添加进path: [1, 2, 3]index:3  path: [1, 2, 3]添加进ans: [1, 2, 3]移除path中: 3移除后path: [1, 2]========================index2结束移除path中: 2移除后path: [1]j:2添加进path: [1, 3]index:3  path: [1, 3]添加进ans: [1, 3]移除path中: 3移除后path: [1]========================index1结束移除path中: 1移除后path: []j:1添加进path: [2]index:2  path: [2]添加进ans: [2]========================index:2j:2添加进path: [2, 3]index:3  path: [2, 3]添加进ans: [2, 3]移除path中: 3移除后path: [2]========================index2结束移除path中: 2移除后path: []j:2添加进path: [3]index:3  path: [3]添加进ans: [3]移除path中: 3移除后path: []========================index0结束

DP

贪心