题目列表

前中后序遍历

  • 144. 二叉树的前序遍历
  • 94. 二叉树的中序遍历
  • 145. 二叉树的后序遍历

  • 剑指 Offer 54. 二叉搜索树的第k大节点

    层序遍历

  • 102. 二叉树的层序遍历

  • 103. 二叉树的锯齿形层序遍历
  • 199. 二叉树的右视图

  • 958. 二叉树的完全性检验

    构造二叉树

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

    DFS

  • 104. 二叉树的最大深度

  • 113. 路径总和 II
  • 112. 路径总和

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

    递归+非递归

  • 226. 翻转二叉树

  • 101. 对称二叉树

  • 98. 验证二叉搜索树

    递归流

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

  • 110. 平衡二叉树【自顶向下，自底向上】
  • 124. 二叉树中的最大路径和

  • 543. 二叉树的直径

    具体代码

    前中后序遍历

    144. 二叉树的前序遍历

    1. class Solution {
    2.   public List<Integer> preorderTraversal(TreeNode root) {
    3.       List<Integer> res = new ArrayList<>();
    4.       if(root == null) return res;
    5.       Stack<TreeNode> stk = new Stack<>();
    6.       TreeNode cur = root;
    7.       while(!stk.isEmpty() || cur != null){
    8.           if(cur != null){
    9.               res.add(cur.val);
    10.               stk.push(cur);
    11.               cur = cur.left;
    12.           }else{
    13.               TreeNode node = stk.pop();
    14.               cur = node.right;
    15.           }
    16.       }
    17.       return res;
    18.   }
    19. }

    94. 二叉树的中序遍历

    1. class Solution {
    2.   public List<Integer> inorderTraversal(TreeNode root) {
    3.       List<Integer> res = new ArrayList<>();
    4.       if(root == null) return res;
    5.       Stack<TreeNode> stk = new Stack<>();
    6.       TreeNode cur = root;
    7.       while(!stk.isEmpty() || cur != null){
    8.           if(cur != null){
    9.               stk.add(cur);
    10.               cur = cur.left;
    11.           }else{
    12.               TreeNode node = stk.pop();
    13.               res.add(node.val);
    14.               cur = node.right;
    15.           }
    16.       }
    17.       return res;
    18.   }
    19. }

    145. 二叉树的后序遍历

  • 还要反转一下，不太行。。。

    1. class Solution {
    2.   public List<Integer> postorderTraversal(TreeNode root) {
    3.       List<Integer> res = new ArrayList<>();
    4.       if(root == null) return res;
    5.       Stack<TreeNode> stk = new Stack<>();
    6.       TreeNode cur = root;
    7.       while(!stk.isEmpty() || cur != null){
    8.           if(cur != null){
    9.               res.add(cur.val);
    10.               stk.push(cur);
    11.               cur = cur.right;
    12.           }else{
    13.               TreeNode node = stk.pop();
    14.               cur = node.left;
    15.           }
    16.       }
    17.       Collections.reverse(res);
    18.       return res;
    19.   }
    20. }

    剑指 Offer 54. 二叉搜索树的第k大节点

    1. class Solution {
    2.   public int kthLargest(TreeNode root, int k) {
    3.       int t = 1;
    4.       Stack<TreeNode> stk = new Stack<>();
    5.       TreeNode cur = root;
    6.       while(!stk.isEmpty() || cur != null){
    7.           if(cur != null){
    8.               stk.push(cur);
    9.               cur = cur.right;
    10.           }else{
    11.               TreeNode node = stk.pop();
    12.               if(t == k) return node.val;
    13.               t++;
    14.               cur = node.left;
    15.           }
    16.       }
    17.       return -1;
    18.   }
    19. }

    层序遍历

    102. 二叉树的层序遍历

    1. class Solution {
    2.   public List<List<Integer>> levelOrder(TreeNode root) {
    3.       List<List<Integer>> res = new ArrayList<>();
    4.       if(root == null) return res;
    5.       Queue<TreeNode> q = new LinkedList<>();
    6.       q.offer(root);
    7.       while(!q.isEmpty()){
    8.           int x = q.size();
    9.           ArrayList<Integer> tmp = new ArrayList<>();
    10.           for(int i = 0; i < x; i++){
    11.               TreeNode node = q.poll();
    12.               tmp.add(node.val);
    13.               if(node.left != null) q.offer(node.left);
    14.               if(node.right != null) q.offer(node.right);
    15.           }
    16.           res.add(tmp);
    17.       }
    18.       return res;
    19.   }
    20. }

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

    1. class Solution {
    2.   public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
    3.       List<List<Integer>> res = new ArrayList<>();
    4.       if(root == null) return res;
    5.       Queue<TreeNode> q = new LinkedList<>();
    6.       q.offer(root);
    7.       int level = 1;
    8.       while(!q.isEmpty()){
    9.           int x = q.size();
    10.           ArrayList<Integer> tmp = new ArrayList<>();
    11.           for(int i = 0; i < x; i++){
    12.               TreeNode node = q.poll();
    13.               if(level % 2 != 0){
    14.                   tmp.add(node.val);
    15.               }else{
    16.                   tmp.add(0, node.val);
    17.               }
    19.               if(node.left != null) q.offer(node.left);
    20.               if(node.right != null) q.offer(node.right);
    21.           }
    22.           res.add(tmp);
    23.           level++;
    24.       }
    25.       return res;
    26.   }
    27. }

    199. 二叉树的右视图

    1. class Solution {
    2.   public List<Integer> rightSideView(TreeNode root) {
    3.       List<Integer> res = new ArrayList<>();
    4.       if(root == null) return res;
    5.       Queue<TreeNode> q = new LinkedList<>();
    6.       q.offer(root);
    7.       while(!q.isEmpty()){
    8.           int x = q.size();
    9.           for(int i = 0 ; i < x; i++){
    10.               TreeNode node = q.poll();
    11.               if(i == x - 1) res.add(node.val);
    12.               if(node.left != null) q.offer(node.left);
    13.               if(node.right != null) q.offer(node.right);
    14.           }
    15.       }
    16.       return res;
    17.   }
    18. }

    958. 二叉树的完全性检验

    1. class Solution {
    2.   public boolean isCompleteTree(TreeNode root) {
    3.       boolean f = false;
    4.       Queue<TreeNode> q = new LinkedList<>();
    5.       q.offer(root);
    6.       while(!q.isEmpty()){
    7.           TreeNode node = q.poll();
    8.           if(f == true && node != null) return false;
    9.           if(node == null){
    10.               f = true;
    11.               continue;
    12.           }
    13.           q.offer(node.left);
    14.           q.offer(node.right);
    15.       }
    16.       return true;
    17.   }
    18. }

    构造二叉树

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

  • if(pl > pr) return null; 递归出口不能忘

  • 不能写成 pl >= pr

    1. class Solution {
    2.   Map<Integer, Integer> map = new HashMap<>();
    3.   public TreeNode makeTree(int[] pre, int pl, int pr, int[] in, int il, int ir){
    4.       if(pl > pr) return null;
    5.       int x = pre[pl];
    6.       TreeNode root = new TreeNode(x);
    7.       int k = map.get(x);
    8.       root.left = makeTree(pre, pl + 1, k - il + pl, in, il, k - 1);
    9.       root.right = makeTree(pre, k - il + pl + 1, pr, in, k + 1, ir);
    10.       return root;
    11.   }
    12.   public TreeNode buildTree(int[] preorder, int[] inorder) {
    13.       for(int i = 0; i < inorder.length; i++) map.put(inorder[i], i);
    14.       return makeTree(preorder, 0, preorder.length - 1, inorder, 0, inorder.length - 1);
    15.   }
    16. }

    DFS

    104. 二叉树的最大深度

    1. class Solution {
    2.   int res = 0;
    3.   public void dfs(TreeNode root, int d){
    4.       if(root.left == null && root.right == null) {
    5.           res = Math.max(res, d);
    6.           return;
    7.       }
    8.       if(root.left != null) dfs(root.left, d + 1);
    9.       if(root.right != null) dfs(root.right, d + 1);
    10.   }
    11.   public int maxDepth(TreeNode root) {
    12.       if(root == null) return 0;
    13.       dfs(root, 1);
    14.       return res;
    15.   }
    16. }

    113. 路径总和 II

    1. class Solution {
    2.   List<List<Integer>> res;
    3.   public void dfs(TreeNode root, int sum, int targetSum, ArrayList tmp){
    4.       if(root.left == null && root.right == null){
    5.           if(sum == targetSum) res.add(new ArrayList(tmp));
    6.           return;
    7.       }
    8.       if(root.left != null){
    9.           tmp.add(root.left.val);
    10.           dfs(root.left, sum + root.left.val, targetSum, tmp);
    11.           tmp.remove(tmp.size() - 1);
    12.       }
    13.       if(root.right != null){
    14.           tmp.add(root.right.val);
    15.           dfs(root.right, sum + root.right.val, targetSum, tmp);
    16.           tmp.remove(tmp.size() - 1);
    17.       }
    18.   }
    19.   public List<List<Integer>> pathSum(TreeNode root, int targetSum) {
    20.       res = new ArrayList<>();
    21.       if(root == null) return res;
    22.       ArrayList<Integer> tmp = new ArrayList<>();
    23.       tmp.add(root.val);
    24.       dfs(root, root.val, targetSum, tmp);
    25.       return res;
    26.   }
    27. }

    112. 路径总和

    1. class Solution {
    2.   boolean f = false;
    3.   public void dfs(TreeNode root, int sum, int targetSum){
    4.       if(root.left == null && root.right == null){
    5.           if(sum == targetSum) {
    6.               f = true;
    7.               return;
    8.           }
    9.       }
    10.       if(f) return;
    11.       if(root.left != null) dfs(root.left, sum + root.left.val, targetSum);
    12.       if(root.right != null) dfs(root.right, sum + root.right.val, targetSum);
    13.   }
    14.   public boolean hasPathSum(TreeNode root, int targetSum) {
    15.       if(root == null) return false;
    16.       dfs(root, root.val, targetSum);
    17.       return f;
    18.   }
    19. }

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

    1. class Solution {
    2.   int res = 0;
    3.   public void dfs(TreeNode root, int tmp){
    4.       if(root.left == null && root.right == null){
    5.           res += tmp;
    6.           return;
    7.       }
    8.       if(root.left != null) dfs(root.left, tmp * 10 + root.left.val);
    9.       if(root.right != null) dfs(root.right, tmp * 10 + root.right.val);
    10.   }
    11.   public int sumNumbers(TreeNode root) {
    12.       dfs(root, root.val);
    13.       return res;
    14.   }
    15. }

    递归+非递归

    226. 翻转二叉树

    递归

    1. class Solution {
    2.   public void reverse(TreeNode root){
    3.       if(root == null) return;
    4.       TreeNode tmp = root.left;
    5.       root.left = root.right;
    6.       root.right = tmp;
    7.       reverse(root.left);
    8.       reverse(root.right);
    9.   }
    10.   public TreeNode invertTree(TreeNode root) {
    11.       reverse(root);
    12.       return root;
    13.   }
    14. }

    非递归

    1. class Solution {
    2.   public TreeNode invertTree(TreeNode root) {
    3.       if(root == null) return null;
    4.       Queue<TreeNode> q = new LinkedList<>();
    5.       q.offer(root);
    6.       while(!q.isEmpty()){
    7.           TreeNode node = q.poll();
    8.           TreeNode tmp = node.left;
    9.           node.left = node.right;
    10.           node.right = tmp;
    11.           if(node.left != null) q.offer(node.left);
    12.           if(node.right != null) q.offer(node.right);
    13.       }
    14.       return root;
    15.   }
    16. }

    101. 对称二叉树

    递归

    1. class Solution {
    2.   public boolean judge(TreeNode l, TreeNode r){
    3.       if(l == null && r == null) return true;
    4.       if(l == null || r == null) return false;
    5.       if(l.val != r.val) return false;
    6.       return judge(l.left, r.right)&&judge(l.right, r.left);
    7.   }
    8.   public boolean isSymmetric(TreeNode root) {
    9.       if(root == null) return true;
    10.       return judge(root.left, root.right);
    11.   }
    12. }

    非递归

    1. class Solution {
    2.   public boolean isSymmetric(TreeNode root) {
    3.       if(root == null) return true;
    4.       Stack<TreeNode> stk = new Stack<>();
    5.       stk.push(root.left);
    6.       stk.push(root.right);
    7.       while(!stk.isEmpty()){
    8.           TreeNode l = stk.pop();
    9.           TreeNode r = stk.pop();
    10.           if(l == null && r == null) continue;
    11.           if(l == null || r == null) return false;
    12.           if(l.val != r.val) return false;
    14.           stk.push(l.left);
    15.           stk.push(r.right);
    16.           stk.push(l.right);
    17.           stk.push(r.left);
    18.       }
    19.       return true;
    20.   }
    21. }

    98. 验证二叉搜索树

    非递归，中序为升序判断

    1. class Solution {
    2.   public boolean isValidBST(TreeNode root) {
    3.       if(root == null) return true;
    4.       double pre = -Double.MAX_VALUE;
    5.       Stack<TreeNode> stk = new Stack<>();
    6.       TreeNode cur = root;
    7.       while(!stk.isEmpty() || cur != null){
    8.           if(cur != null){
    9.               stk.push(cur);
    10.               cur = cur.left;
    11.           }else{
    12.               TreeNode node = stk.pop();
    13.               if(node.val <= pre) return false;
    14.               pre = node.val;
    15.               cur = node.right;
    16.           }
    17.       }
    18.       return true;
    19.   }
    20. }

    递归

    1. class Solution {
    2.   public boolean isValidBST(TreeNode root) {
    3.       if(root == null) return true;
    4.       return judge(root, Long.MIN_VALUE, Long.MAX_VALUE);
    5.   }
    6.   public boolean judge(TreeNode root, long low, long up){
    7.       if(root == null) return true;
    8.       if(root.val <= low || root.val >= up) return false;
    9.       return judge(root.left, low, root.val)&&judge(root.right, root.val, up);
    10.   }
    11. }

    递归流

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

    1. class Solution {
    2.   public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
    3.       if(root == null || root == p || root == q) return root;
    4.       TreeNode l = lowestCommonAncestor(root.left, p, q);
    5.       TreeNode r = lowestCommonAncestor(root.right, p, q);
    6.       if(l != null && r != null) return root;
    7.       else if(l != null) return l;
    8.       else return r;
    9.   }
    10. }
    1. class Solution {
    2.   /**
    3.       注意p,q必然存在树内, 且所有节点的值唯一!!!
    4.       递归思想, 对以root为根的(子)树进行查找p和q, 如果root == null || p || q 直接返回root
    5.       表示对于当前树的查找已经完毕, 否则对左右子树进行查找, 根据左右子树的返回值判断:
    6.       1. 左右子树的返回值都不为null, 由于值唯一左右子树的返回值就是p和q, 此时root为LCA
    7.       2. 如果左右子树返回值只有一个不为null, 说明只有p和q存在与左或右子树中, 最先找到的那个节点为LCA
    8.       3. 左右子树返回值均为null, p和q均不在树中, 返回null
    9.       **/
    10.   public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
    11.       if(root == null || root == p || root == q) return root;
    12.       TreeNode l = lowestCommonAncestor(root.left, p, q);
    13.       TreeNode r = lowestCommonAncestor(root.right, p, q);
    14.       if(l != null && r != null) return root;
    15.       else if(l != null) return l;
    16.       else if(r != null) return r;
    17.       else return null;
    18.   }
    19. }

    110. 平衡二叉树

    自顶向下，有大量重复计算

    1. class Solution {
    2.   public int getDepth(TreeNode root){
    3.       if(root == null) return 0;
    4.       int l = getDepth(root.left);
    5.       int r = getDepth(root.right);
    6.       return Math.max(l, r) + 1;
    7.   }
    8.   public boolean isBalanced(TreeNode root) {
    9.       if(root == null) return true;
    10.       int l = getDepth(root.left);
    11.       int r = getDepth(root.right);
    12.       if(Math.abs(l - r) > 1) return false;
    13.       return isBalanced(root.left)&&isBalanced(root.right);
    14.   }
    15. }

    自底向上

    1. class Solution {
    2.   public boolean isBalanced(TreeNode root) {
    3.       return judge(root) >= 0;
    4.   }
    5.   public int judge(TreeNode root){
    6.       if(root == null) return 0;
    7.       int l = judge(root.left);
    8.       int r = judge(root.right);
    9.       if(l >= 0 && r >= 0 && Math.abs(l - r) <= 1){
    10.           return Math.max(l, r) + 1;
    11.       }else{
    12.           return -1;
    13.       }
    14.   }
    15. }

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

    1. class Solution {
    2.   int res = Integer.MIN_VALUE;
    3.   public int getRes(TreeNode root){
    4.       if(root == null) return 0;
    5.       int l = Math.max(0, getRes(root.left));
    6.       int r = Math.max(0, getRes(root.right));
    7.       res = Math.max(res, l + r + root.val);
    8.       return Math.max(l, r) + root.val;
    9.   }
    10.   public int maxPathSum(TreeNode root) {
    11.       if(root == null) return 0;
    12.       getRes(root);
    13.       return res;
    14.   }
    15. }

    543. 二叉树的直径

    class Solution {
  int res = Integer.MIN_VALUE;
  public int getRes(TreeNode root){
      if(root == null) return 0;
      int l = root.left == null ? 0: getRes(root.left) + 1;
      int r = root.right == null ? 0: getRes(root.right) + 1;
      res = Math.max(res, l + r);
      return Math.max(l, r);
  }
  public int diameterOfBinaryTree(TreeNode root) {
      if(root == null) return 0;
      getRes(root);
      return res;
  }
}