二叉树

题型1：二叉树前中后序遍历

144. 二叉树的前序遍历（简单）

递归
  1. class Solution {
  2.     public List<Integer> preorderTraversal(TreeNode root) {
  3.         List<Integer> result = new ArrayList<>();
  4.         doPreOrderTraversal(root, result);
  5.         return result;
  6.     }
  8.     private void doPreOrderTraversal(TreeNode root, List<Integer> list) {
  9.         if(root == null) {
  10.             return;
  11.         }
  12.         list.add(root.val);
  13.         doPreOrderTraversal(root.left, list);
  14.         doPreOrderTraversal(root.right, list);
  15.     }
  16. }

迭代

解题思路：

  1. class Solution {
  3.     class StackFrame {
  4.         private int status;
  6.         private TreeNode node;
  8.         public StackFrame(int status, TreeNode node) {
  9.             this.status = status;
  10.             this.node = node;
  11.         } 
  12.     }
  14.     public List<Integer> preorderTraversal(TreeNode root) {
  15.         List<Integer> result = new ArrayList<>();
  16.         Stack<StackFrame> stack = new Stack<>();
  17.         TreeNode p = root;
  18.         while(true) {
  19.             // 一路向左
  20.             while(p != null) {
  21.                 stack.push(new StackFrame(1, p));
  22.                 result.add(p.val);
  23.                 p = p.left;
  24.             }
  25.             while(!stack.isEmpty() && stack.peek().status == 2) {
  26.                 p = stack.pop().node;
  27.             }
  28.             if(stack.isEmpty()) {
  29.                 break;
  30.             }
  31.             stack.peek().status = 2;
  32.             p = stack.peek().node.right;
  33.         }
  34.         return result;
  35.     }
  36. }

94. 二叉树的中序遍历 （简单）

递归
  1. class Solution {
  2.     public List<Integer> inorderTraversal(TreeNode root) {
  3.         List<Integer> result = new ArrayList<>();
  4.         doInorderTraversal(root, result);
  5.         return result;
  6.     }
  8.     private void doInorderTraversal(TreeNode root, List<Integer> list) {
  9.         if(root == null) {
  10.             return;
  11.         }
  12.         doInorderTraversal(root.left, list);
  13.         list.add(root.val);
  14.         doInorderTraversal(root.right, list);
  15.     }
  16. }

迭代
  1. class Solution {
  3.     class SFrame {
  4.         private int status;
  6.         private TreeNode node;
  8.         public SFrame(int status, TreeNode node) {
  9.             this.status = status;
  10.             this.node = node;
  11.         }
  12.     }
  14.     public List<Integer> inorderTraversal(TreeNode root) {
  15.         List<Integer> result = new ArrayList<>();
  16.         Stack<SFrame> stack = new Stack<>();
  17.         while(true) {
  18.             // 一路向左
  19.             while(root != null) {
  20.                 stack.push(new SFrame(1, root));
  21.                 root = root.left;
  22.             }
  23.             while(!stack.isEmpty() && stack.peek().status == 2) {
  24.                 stack.pop();
  25.             }
  26.             // 栈空证明迭代完成，结束死循环
  27.             if(stack.isEmpty()) {
  28.                 break;
  29.             }
  30.             stack.peek().status = 2;
  31.             // 中序遍历
  32.             result.add(stack.peek().node.val);
  33.             root = stack.peek().node.right;
  34.         }
  35.         return result;
  36.     }
  37. }

145. 二叉树的后序遍历（简单）

递归
  1. class Solution {
  2.     public List<Integer> postorderTraversal(TreeNode root) {
  3.         List<Integer> result = new ArrayList<>();
  4.         doPostOrderTraversal(root, result);
  5.         return result;
  6.     }
  8.     private void doPostOrderTraversal(TreeNode root, List<Integer> list) {
  9.         if(root == null) {
  10.             return;
  11.         }
  12.         doPostOrderTraversal(root.left, list);
  13.         doPostOrderTraversal(root.right, list);
  14.         list.add(root.val);
  15.     }
  16. }

迭代
  1. class Solution {
  3.     class SFrame {
  4.         private int status;
  6.         private TreeNode node;
  8.         public SFrame(int status, TreeNode node) {
  9.             this.status = status;
  10.             this.node = node;
  11.         }
  12.     }
  14.     public List<Integer> postorderTraversal(TreeNode root) {
  15.         List<Integer> result = new ArrayList<>();
  16.         Stack<SFrame> stack = new Stack<>();
  17.         while(true) {
  18.             // 一路向左
  19.             while(root != null) {
  20.                 stack.push(new SFrame(1, root));
  21.                 root = root.left;
  22.             }
  23.             while(!stack.isEmpty() && stack.peek().status == 2) {
  24.                 result.add(stack.pop().node.val);
  25.             }
  26.             // 栈空证明迭代完成，结束死循环
  27.             if(stack.isEmpty()) {
  28.                 break;
  29.             }
  30.             stack.peek().status = 2;
  31.             // 中序遍历
  32.             root = stack.peek().node.right;
  33.         }
  34.         return result;
  35.     }
  36. }

589. N 叉树的前序遍历（简单）例题

递归
  1. class Solution {
  2.     public List<Integer> preorder(Node root) {
  3.         List<Integer> res = new ArrayList<>();
  4.         doPreOrder(root, res);
  5.         return res;
  6.     }
  8.     private void doPreOrder(Node root, List<Integer> list) {
  9.         if(root == null) {
  10.             return;
  11.         }
  12.         list.add(root.val);
  13.         for(Node child : root.children) {
  14.             doPreOrder(child, list);
  15.         }
  16.     }
  17. }

迭代
  1. class Solution {
  3.     public List<Integer> preorder(Node root) {
  4.         List<Integer> result = new ArrayList<>();
  5.         if(root == null) {
  6.             return result;
  7.         }
  8.         LinkedList<Node> stack = new LinkedList<>();
  9.         stack.add(root);         
  10.         while(!stack.isEmpty()) {
  11.             Node cur = stack.pollLast();
  12.             result.add(cur.val);
  13.             Collections.reverse(cur.children);
  14.             stack.addAll(cur.children);
  15.         }
  16.         return result;
  17.     }
  18. }

590. N 叉树的后序遍历（简单）

递归
  1. class Solution {
  2.     public List<Integer> postorder(Node root) {
  3.         List<Integer> result = new ArrayList<>();
  4.         if(root == null) {
  5.             return result;
  6.         }
  7.         doPostOrder(root, result);
  8.         result.add(root.val);
  9.         return result;
  10.     }
  12.     private void doPostOrder(Node root, List<Integer> list) {
  13.         if(root == null) {
  14.             return;
  15.         }
  16.         for(Node child : root.children) {
  17.             doPostOrder(child, list);
  18.             list.add(child.val);
  19.         }
  20.     }
  21. }

迭代

解题思路：

  1. class Solution {
  3.     class SFrame {
  4.         private Node node;
  6.         private int status;
  8.         public SFrame(int status, Node node) {
  9.             this.status = status;
  10.             this.node = node;
  11.         }
  12.     }
  14.     public List<Integer> postorder(Node root) {
  15.         List<Integer> result = new ArrayList<>();
  16.         if(root == null) {
  17.             return result;
  18.         }
  19.         LinkedList<SFrame> stack = new LinkedList<>();
  20.         stack.add(new SFrame(1, root));
  21.         while(!stack.isEmpty()) {
  22.             Node node = stack.peekLast().node;
  23.             stack.peekLast().status = 2;
  24.             Collections.reverse(node.children);
  25.             for(Node n : node.children) {
  26.                 stack.add(new SFrame(1, n));
  27.             }
  28.             while(!stack.isEmpty() && stack.peekLast().status == 2) {
  29.                 result.add(stack.pollLast().node.val);
  30.             }
  31.         }
  32.         return result;
  33.     }
  34. }

题型2：二叉树按层遍历

剑指 Offer 32 - I. 从上到下打印二叉树（中等）例题

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

102. 二叉树的层序遍历（中等）

利用队列实现层析遍历
  1. class Solution {
  2.     public List<List<Integer>> levelOrder(TreeNode root) {
  3.         List<List<Integer>> resList = new ArrayList<>();
  4.         if(root == null) {
  5.             return resList;
  6.         }
  7.         LinkedList<TreeNode> queue = new LinkedList<>();
  8.         queue.offer(root);
  9.         while(!queue.isEmpty()) {
  10.             int size = queue.size();
  11.             List<Integer> list = new ArrayList<>();
  12.             for(int i = 0; i < size; i++) {
  13.                 TreeNode node = queue.poll();
  14.                 list.add(node.val);
  15.                 if(node.left != null) {
  16.                     queue.offer(node.left);
  17.                 }
  18.                 if(node.right != null) {
  19.                     queue.offer(node.right);
  20.                 }
  21.             }
  22.             resList.add(list); 
  23.         }
  24.         return resList;
  25.     }
  26. }

递归-二叉树后序遍历
  1. class Solution {
  2.     public List<List<Integer>> levelOrder(TreeNode root) {
  3.         List<List<Integer>> resList = new ArrayList<>();
  4.         if(root == null) {
  5.             return resList;
  6.         }
  7.         recursion(root, resList, 0);
  8.         return resList;
  9.     }
  11.     private void recursion(TreeNode root, List<List<Integer>> resList, int level) {
  12.         if(root == null) {
  13.             return; 
  14.         }
  15.         // 预先创建list
  16.         if(resList.size() <= level) {
  17.             resList.add(new ArrayList<>());
  18.         }
  19.         // 后序遍历
  20.         recursion(root.left, resList, level + 1);
  21.         recursion(root.right, resList, level + 1);
  22.         // 利用下标来实现层次添加
  23.         resList.get(level).add(root.val);
  24.     }
  25. }

剑指 Offer 32 - III. 从上到下打印二叉树 III （中等）

队列
  1. class Solution {
  2.     public List<List<Integer>> levelOrder(TreeNode root) {
  3.         List<List<Integer>> resList = new ArrayList<>();
  4.         if(root == null) {
  5.             return resList;
  6.         }
  7.         Queue<TreeNode> queue = new LinkedList<>();
  8.         queue.offer(root);
  9.         int flag = 0;
  10.         while(!queue.isEmpty()) {
  11.             LinkedList<Integer> list = new LinkedList<>();
  12.             int size = queue.size();
  13.             for(int i = 0; i < size; i++) {
  14.                 TreeNode node = null;
  15.                 node = queue.poll();
  16.                 if((flag & 1) == 1) {
  17.                     list.offerFirst(node.val);
  18.                 } else {
  19.                     list.offerLast(node.val);
  20.                 }
  21.                 if(node.left != null) {
  22.                     queue.offer(node.left);
  23.                 }
  24.                 if(node.right != null) {
  25.                     queue.offer(node.right);
  26.                 }
  27.             }
  28.             resList.add(list);
  29.             flag++;            
  30.         }
  31.         return resList;
  32.     }
  33. }

429. N 叉树的层序遍历（中等）

队列
  1. class Solution {
  2.     public List<List<Integer>> levelOrder(Node root) {
  3.         List<List<Integer>> resList = new ArrayList<>();
  4.         if(root == null) {
  5.             return resList;
  6.         }
  7.         Queue<Node> queue = new LinkedList<>();
  8.         queue.offer(root);
  9.         while(!queue.isEmpty()) {
  10.             List<Integer> list = new ArrayList<>();
  11.             int size = queue.size();
  12.             for(int i = 0; i < size; i++) {
  13.                 Node node = queue.poll();
  14.                 for(Node child : node.children) {
  15.                     queue.offer(child);
  16.                 }
  17.                 list.add(node.val);
  18.             }
  19.             resList.add(list);
  20.         }
  21.         return resList;
  22.     }
  23. }

递归
  1. class Solution {
  2.     public List<List<Integer>> levelOrder(Node root) {
  3.         List<List<Integer>> res = new ArrayList<>();
  4.         doLevelOrder(root, res, 0);
  5.         return res;
  6.     }
  8.     private void doLevelOrder(Node root, List<List<Integer>> list, int level) {
  9.         if(root == null) {
  10.             return;
  11.         }
  12.         if(list.size() <= level) {
  13.             list.add(new ArrayList<Integer>());
  14.         }
  15.         list.get(level).add(root.val);
  16.         for(Node child : root.children) {
  17.             doLevelOrder(child, list, level + 1);
  18.         }
  19.     }
  20. }

513. 找树左下角的值（中等）

DFS-深度优先遍历
  1. class Solution {
  2.     private int depth = Integer.MIN_VALUE;
  4.     private int res = 0;
  6.     public int findBottomLeftValue(TreeNode root) {
  7.         dfs(root, 0);
  8.         return res;
  9.     }
  11.     private void dfs(TreeNode root, int d) {
  12.         if(root != null) {
  13.             if(root.left == null && root.right == null) {
  14.                 if(depth < d) {
  15.                     depth = d;
  16.                     res = root.val;
  17.                 }
  18.             }
  19.             dfs(root.left, d + 1);
  20.             dfs(root.right, d + 1);
  21.         }
  22.     }
  23. }

递归
  1. class Solution {
  2.     public int findBottomLeftValue(TreeNode root) {
  3.         List<List<Integer>> list = new ArrayList<>();
  4.         postOrder(root, list, 0);
  5.         return list.get(list.size() - 1).get(0);
  6.     }
  8.     private void postOrder(TreeNode root, List<List<Integer>> list, int level) {
  9.         if(root == null) {
  10.             return;
  11.         }
  12.         if(list.size() <= level) {
  13.             list.add(new ArrayList<>());
  14.         }
  15.         postOrder(root.left, list, level + 1);
  16.         postOrder(root.right, list, level + 1);
  17.         list.get(level).add(root.val);
  18.     }
  19. }

题型3：二叉树上的递归

104. 二叉树的最大深度（简单）例题

  1. class Solution {
  3.     public int maxDepth(TreeNode root) {
  4.         if(root == null) {
  5.             return 0;
  6.         }
  7.         int ld = maxDepth(root.left);
  8.         int rd = maxDepth(root.right);
  9.         return Math.max(ld, rd)  + 1;
  10.     }
  11. }

559. N 叉树的最大深度（简单）

  1. class Solution {
  2.     public int maxDepth(Node root) {
  3.         if(root == null) {
  4.             return 0;
  5.         }
  6.         if(root.children == null || root.children.isEmpty()){
  7.             return 1;
  8.         }
  9.         int res = 0;
  10.         for(Node child : root.children) {
  11.             res = Math.max(res, maxDepth(child));
  12.         }
  13.         return res + 1;
  14.     }
  15. }

剑指 Offer 55 - II. 平衡二叉树（中等）例题

解题思路：

  1. class Solution {
  2.     private boolean flag = true;
  3.     public boolean isBalanced(TreeNode root) {
  4.         maxDepth(root);
  5.         if(!flag) {
  6.             return false;
  7.         }
  8.         return true;
  9.     }
  11.     private int maxDepth(TreeNode root) {
  12.         if(root == null) {
  13.             return 0;
  14.         }
  15.         int ld = maxDepth(root.left);
  16.         if(!flag) {
  17.             return 0;
  18.         }
  19.         int rd = maxDepth(root.right);
  20.         if(!flag) {
  21.             return 0;
  22.         }
  23.         if(Math.abs(ld - rd) > 1) {
  24.             flag = false;
  25.         }
  26.         return Math.max(ld, rd) + 1;
  27.     }
  28. }

617. 合并二叉树（简单）

  1. class Solution {
  2.     public TreeNode mergeTrees(TreeNode root1, TreeNode root2) {
  3.         if(root1 == null && root2 == null) {
  4.             return null;
  5.         }
  6.         if(root1 == null) {
  7.             return root2;
  8.         }
  10.         if(root2 == null) {
  11.             return root1;
  12.         }
  13.         TreeNode root = new TreeNode(root1.val + root2.val);
  14.         root.left = mergeTrees(root1.left, root2.left);
  15.         root.right = mergeTrees(root1.right, root2.right);
  16.         return root;
  17.     }
  18. }

226. 翻转二叉树 （简单）

解题思路：
递归公式：

  • 原问题：交换根节点的左右子树的根节点
  • 分解成子问题：
      1. 交换左子树的左右子树的根节点
      1. 交换右子树的左右子树的根节点
        1. class Solution {
        2. public TreeNode invertTree(TreeNode root) {
        3. if(root == null) {
        4.     return null;
        5. }
        6. TreeNode tmp = root.left;
        7. root.left = root.right;
        8. root.right = tmp;
        9. root.left = invertTree(root.left);
        10. root.right = invertTree(root.right);
        11. return root;
        12. }
        13. }

101. 对称二叉树（中等）

递归
  1. class Solution {
  2.     private boolean flag = true;
  4.     public boolean isSymmetric(TreeNode root) {
  5.         if(root.left == null && root.right == null) {
  6.             return flag;
  7.         }
  8.         dfs(root.left, root.right);
  9.         return flag;
  10.     }
  12.     private void dfs(TreeNode lNode, TreeNode rNode) {
  13.         if(lNode == null && rNode == null) {
  14.             return;
  15.         }
  16.         if(lNode == null || rNode == null) {
  17.             flag = false;
  18.             return;
  19.         }
  20.         if(lNode.val != rNode.val) {
  21.             flag = false;
  22.         }   
  23.         dfs(lNode.left, rNode.right);
  24.         dfs(lNode.right, rNode.left);
  25.     } 
  26. }

迭代

98. 验证二叉搜索树（中等）

中序遍历

解题思路：BST中序遍历，当前遍历的节点的值一定比上一个节点的值大。

  1. /**
  2.  * Definition for a binary tree node.
  3.  * public class TreeNode {
  4.  *     int val;
  5.  *     TreeNode left;
  6.  *     TreeNode right;
  7.  *     TreeNode() {}
  8.  *     TreeNode(int val) { this.val = val; }
  9.  *     TreeNode(int val, TreeNode left, TreeNode right) {
  10.  *         this.val = val;
  11.  *         this.left = left;
  12.  *         this.right = right;
  13.  *     }
  14.  * }
  15.  */
  16. class Solution {
  17.     private long pre = Long.MIN_VALUE;
  18.     public boolean isValidBST(TreeNode root) {
  19.         if(root == null) {
  20.             return true;
  21.         }
  22.         if(!isValidBST(root.left)) {
  23.             return false;
  24.         }
  25.         long target = (long)root.val;
  26.         if(pre >= target) {
  27.             return false;
  28.         }
  29.         pre = target;
  30.         return isValidBST(root.right);
  31.     }
  32. }

递归

解题思路：

  1. BST 任意节点的值都比其左子树的节点值大，比其右子树节点的值小。
  2. 设置上界值upper、下界值lower，那么任意节点 node 的值都要满足 lower < node.val < upper。

  3. 对于左子树的上界值 upper = node.val，下界值为负无穷，右子树的下界值 lower = node.val，上界值为正无穷。

    1. /**
    2. * Definition for a binary tree node.
    3. * public class TreeNode {
    4. *     int val;
    5. *     TreeNode left;
    6. *     TreeNode right;
    7. *     TreeNode() {}
    8. *     TreeNode(int val) { this.val = val; }
    9. *     TreeNode(int val, TreeNode left, TreeNode right) {
    10. *         this.val = val;
    11. *         this.left = left;
    12. *         this.right = right;
    13. *     }
    14. * }
    15. */
    16. class Solution {
    17.  public boolean isValidBST(TreeNode root) {
    18.      return isValidBST(root, Long.MIN_VALUE, Long.MAX_VALUE);
    19.  }
    21.  private boolean isValidBST(TreeNode node, long low, long upper) {
    22.      if(node == null) {
    23.          return true;
    24.      }
    25.      if(low < node.val && node.val < upper) {
    26.          return isValidBST(node.left, low, node.val) && isValidBST(node.right, node.val, upper);
    27.      }
    28.      return false;
    29.  }
    30. }

题型4：二叉查找树

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

递归-中序遍历
  1. class Solution {
  2.     public int kthLargest(TreeNode root, int k) {
  3.         List<Integer> list = new ArrayList<>();
  4.         inOrder(root, list);
  5.         int size = list.size();
  6.         int idx = size - k;
  7.         return list.get(idx);
  8.     }
  10.     private void inOrder(TreeNode root, List<Integer> list) {
  11.         if(root == null) {
  12.             return;
  13.         }
  14.         inOrder(root.left, list);
  15.         list.add(root.val);
  16.         inOrder(root.right, list);
  17.     }
  18. }

时间复杂度：O(n)
空间复杂度：O(n)

中序遍历-剪枝优化
  1. class Solution {
  2.     private int count = 0;
  4.     private int res = Integer.MIN_VALUE;
  6.     public int kthLargest(TreeNode root, int k) {
  7.         inOrder(root, k);
  8.         return res;
  9.     }
  11.     private void inOrder(TreeNode root, int k) {
  12.         if(root == null) {
  13.             return;
  14.         }
  16.         inOrder(root.right, k);
  17.         // 剪枝
  18.         if(++count == k) {
  19.             res = root.val;
  20.             return;
  21.         }
  22.         inOrder(root.left, k);
  23.     }
  24. }

时间复杂度：O(n)
空间复杂度：O(1)

538. 把二叉搜索树转换为累加树 （中等）

递归-中序遍历
  1. class Solution {
  2.     private int sum = 0;
  4.     public TreeNode convertBST(TreeNode root) {
  5.         if(root == null) {
  6.             return null;
  7.         } 
  8.         convertBST(root.right);
  9.         sum += root.val;
  10.         root.val = sum;
  11.         convertBST(root.left);
  12.         return root;
  13.     }
  14. }

面试题 04.06. 后继者（中等）

递归-中序遍历
  1. class Solution {
  2.     private TreeNode res, pre, p;
  4.     public TreeNode inorderSuccessor(TreeNode root, TreeNode p) {
  5.         this.p = p;
  6.         dfs(root);
  7.         return res;
  8.     }
  10.     private void dfs(TreeNode root) {
  11.         if(root == null) {
  12.             if(pre == p) {
  13.                 res = null;
  14.             }
  15.             return;
  16.         }
  17.         dfs(root.left);
  18.         if(pre == p) {
  19.             res = root;
  20.         }
  21.         pre = root;
  22.         dfs(root.right);
  23.     }
  24. }