遍历

递归版本（前/中/后）

  1. public static void orderRecursive(TreeNode root) {
  2.     if (root == null)   return ;
  3.     //只要改变访问当前节点的顺序就行
  4.     //1.先序
  5.     System.out.println(root.val);
  6.     preOrderRecursive(root.left);
  7.     //2.中序 System.out.println(root.val);
  8.     preOrderRecursive(root.right);
  9.     //3.后序 System.out.println(root.val);
  10. }

1.先序遍历

非递归

  1. public void preOrderNoRecursive(TreeNode root) {
  2.     if (root == null)   return ;
  3.     Stack<TreeNode> stack = new Stack<>();
  4.     TreeNode curNode = root;
  5.     while (!stack.isEmpty() || curNode != null) {
  6.         while (curNode != null) {
  7.             //访问节点
  8.             stack.push(curNode);
  9.             curNode = curNode.left;
  10.         }
  11.         curNode = stack.pop();
  12.         curNode = curNode.right;
  13.     }
  14. }

2.中序遍历

二叉搜索树的中序遍历刚好是从小到大的顺序，这是比较特殊的一点。

非递归

和先序的类似

  1. public void preOrder(TreeNode root) {
  2.     if (root == null)   return ;
  3.     Stack<TreeNode> stack = new Stack<>();
  4.     TreeNode curNode = root;
  5.     while (!stack.isEmpty() || curNode != null) {
  6.         while (curNode != null) {
  7.             stack.push(curNode);
  8.             curNode = curNode.left;
  9.         }
  10.         //访问节点
  11.         curNode = stack.pop();
  12.         curNode = curNode.right;
  13.     }
  14. }

反序的中序遍历只需要将上面left和right两行代码互换即可，在一些题目中可能会出现，比如538。

Morris中序

空间复杂度为O(1)，核心是找前驱节点，在遍历的过程中树的结构会发生改变，但在遍历后会恢复成遍历前的结构。
需要两个指针，当前指针curNode和前驱指针preNode：

  • 如果左子节点为空，遍历当前节点，并使得当前节点curNode指向右子节点，开始新的遍历就行。
  • 如果左子节点不为空，则当前节点的前驱节点一定位于左子树中，开始寻找左子树中最右侧节点，可能会出现两种情况：
    1. 如果遍历到的最右侧叶节点的右子节点为空，表明该叶节点是curNode的前驱节点，因此把该叶节点的右指针指向当前节点（这样是为了后面遍历到叶节点后还能回到curNode），然后另curNode指向左子节点，开始新的遍历。
    2. 如果遍历到的最右侧节点的右子节点是curNode，表示该左子树已经全部遍历完毕，需要复原，因此将右子节点重新置为空，并遍历curNode。使得当前节点curNode指向右子节点，开始新的遍历就行。
      1. public void morrisInOrder(TreeNode root) {
      2. TreeNode curNode = root, preNode = null;        //注意当前节点curNode的更新只有两处
      3. while (curNode != null) {
      4.   //如果当前节点没有左子树，则遍历然后跳转右子树
      5.   if (curNode.left == null) {
      6.       //遍历curNode
      7.       curNode = curNode.right;
      8.       continue;
      9.   }
      10.   preNode = curNode.left;
      11.   //前驱节点一定在左子树上
      12.   while (preNode.right != null && preNode.right != curNode) {
      13.       preNode = preNode.right;
      14.   }
      15.   if (preNode.right == null) {    //第一次找到前驱节点
      16.       preNode.right = curNode;
      17.       curNode = curNode.left;        //从curNode.left重新开始遍历
      18.   } else {
      19.       preNode.right = null;        //复原
      20.       //遍历curNode
      21.       curNode = curNode.right;
      22.   }
      23. }
      24. }

      3. 后序遍历

      容易理解的方法：(根，左，右) -> (根，右，左) -> (左，右，根)
      1. public List<Integer> postorderTraversal(TreeNode root) {
      2. Stack<TreeNode> stack = new Stack();
      3. List<Integer> postOrderList = new ArrayList(); 
      4. TreeNode curNode = root;
      5. while (!stack.isEmpty() || curNode != null) {
      6.   while (curNode != null) {
      7.       postOrderList.add(curNode.val);
      8.       stack.push(curNode);
      9.       curNode = curNode.right;
      10.   }
      11.   curNode = stack.pop();
      12.   curNode = curNode.left;
      13. }
      14. Collections.reverse(postOrderList);
      15. return postOrderList;
      16. }
      17. public List<Integer> postorderTraversal(TreeNode root) {
      18. Stack<TreeNode> stack = new Stack();
      19. List<Integer> postOrderList = new ArrayList(); 
      20. TreeNode curNode = root, prev = null;
      21. while (!stack.isEmpty() || curNode != null) {
      22.   while (curNode != null) {
      23.       stack.push(curNode);
      24.       curNode = curNode.left;
      25.   }
      26.   curNode = stack.pop();
      27.   if (curNode.right == null || curNode.right == prev) {
      28.       postOrderList.add(curNode.val);
      29.       prev = curNode;
      30.       curNode = null;
      31.   } else {
      32.       stack.push(curNode);
      33.       curNode = curNode.right;
      34.   }
      35. }
      36. return postOrderList;
      37. }

      4. 层次遍历

      116. 填充每个节点的下一个右侧节点指针链接

      重点是空间如何优化为O(1)，需要想到上层节点是一个链表。
      dummy节点能够避免头结点为空的特判情况，代码好看一点。
      1. public Node connect(Node root) {
      2. Node curLevelNode = root;
      3. while (curLevelNode != null) {
      4.   Node nextLevelDummyNode = new Node(-1), nextLevelCurNode = nextLevelDummyNode;
      5.   while (curLevelNode != null) {
      6.       Node left = curLevelNode.left;
      7.       Node right = curLevelNode.right;
      8.       if (left == null)    break;
      9.       nextLevelCurNode.next = left;
      10.       left.next = right;
      11.       nextLevelCurNode = right;
      12.       curLevelNode = curLevelNode.next;
      13.   }
      14.   curLevelNode = nextLevelDummyNode.next;
      15.   nextLevelDummyNode.next = null;
      16. }
      17. return root;
      18. }

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

      相比于上一题，没有了完全二叉树的限制，算是比较通用的，稍微麻烦了一点。
      1. //常规的层次遍历，时间/空间复杂度都是O(n)
      2. public Node connect(Node root) {
      3. if (root == null)   return root;
      4. LinkedList<Node> queue = new LinkedList();
      5. queue.offer(root);
      6. while (!queue.isEmpty()) {
      7.   int size = queue.size();
      8.   while (size-- > 0) {
      9.       Node curNode = queue.poll();
      10.       curNode.next = (size > 0 ? queue.get(0) : null);
      11.       if (curNode.left != null)   queue.offer(curNode.left);
      12.       if (curNode.right != null)   queue.offer(curNode.right);
      13.   }
      14. }
      15. return root;
      16. }
      17. public Node connect(Node root) {
      18. Node curLevelNode = root;
      19. while (curLevelNode != null) {
      20.   Node nextLevelDummyNode = new Node(-1), nextLevelCurNode = nextLevelDummyNode;
      21.   while (curLevelNode != null) {
      22.       Node left = curLevelNode.left;
      23.       Node right = curLevelNode.right;
      24.       if (left != null) {
      25.           nextLevelCurNode.next = left;
      26.           left.next = right;
      27.           nextLevelCurNode = left;
      28.       }
      29.       if (right != null) {
      30.           nextLevelCurNode.next = right;
      31.           nextLevelCurNode = right;
      32.       }
      33.       curLevelNode = curLevelNode.next;
      34.   }
      35.   curLevelNode = nextLevelDummyNode.next;
      36.   nextLevelDummyNode.next = null;
      37. }
      38. return root;
      39. }

      LeetCode

106. 从中序和后序遍历序列中构造二叉树

关键是找出中序节点中根节点所在的位置，然后递归构造，需要注意各种边界条件。

  1. public TreeNode buildTree(int[] inorder, int[] postorder) {
  2.     if (inorder == null || postorder == null)   return null;
  3.     return buildTree(inorder, 0, inorder.length-1, postorder, 0, postorder.length-1);
  4. }
  5. public TreeNode buildTree(int[] inorder, int il, int ir, int[] postorder, int pl, int pr) {
  6.     if (il < 0 || ir >= inorder.length || pl < 0 || pr >= postorder.length)    return null;
  7.     if (ir < il || pr < pl || ir-il != pr-pl) return null;
  8.     int rootIdx = findRootIndex(inorder, il, ir, postorder[pr]);
  9.     if (rootIdx == -1)  return null;
  10.     TreeNode root = new TreeNode(postorder[pr]);
  11.     root.left = buildTree(inorder, il, rootIdx-1, postorder, pl, pl+rootIdx-il-1);
  12.     root.right = buildTree(inorder, rootIdx+1, ir, postorder, pl+rootIdx-il, pr-1);
  13.     return root;
  14. }
  15. public int findRootIndex(int[] inorder, int l, int r, int rootVal) {
  16.     int i = l;
  17.     for (; i <= r; i++) {
  18.         if (inorder[i] == rootVal)  break;
  19.     }
  20.     return i <= r ? i : -1;
  21. }

113. 路径总和 II

  1. List<List<Integer>> res = new ArrayList<>();
  2. public List<List<Integer>> pathSum(TreeNode root, int sum) {
  3.     pathSum(root, sum, new ArrayList<Integer>());
  4.     return res;
  5. }
  6. public void pathSum (TreeNode root, int sum, List<Integer> curPath) {
  7.     if (root == null)   return ;
  8.     sum -= root.val;
  9.     curPath.add(root.val);
  10.     if (root.left == null && root.right == null && sum == 0) {
  11.         res.add(new ArrayList<Integer>(curPath));
  12.         return ;
  13.     }
  14.     pathSum(root.left, sum, curPath);
  15.     pathSum(root.right, sum, curPath);
  16.     curPath.remove(curPath.size()-1);
  17. }

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

  • 所有节点的值都是唯一的。
  • p、q 为不同节点且均存在于给定的二叉搜索树中。

如果没有给出上述的限制的话，感觉边界还挺麻烦的？

  1. public TreeNode lowestCommonAncestorRecursive(TreeNode root, TreeNode p, TreeNode q) {
  2.     if (root == null || p == null || q == null) return null;
  3.     if (root.val > p.val && root.val > q.val)   return lowestCommonAncestor(root.left, p, q);
  4.     if (root.val < p.val && root.val < q.val)   return lowestCommonAncestor(root.right, p, q);
  5.     return root;
  6. }
  7. //二次遍历
  8. public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
  9.     if (root == null || p == null || q == null) return null;
  10.     List<TreeNode> path1 = getPath(root, p), path2 = getPath(root, q);
  11.     TreeNode ancestor = null;
  12.     for (int i = 0; i < path1.size() && i < path2.size(); i++) {
  13.         if (path1.get(i) == path2.get(i))   ancestor = path1.get(i);
  14.         else break;
  15.     }
  16.     return ancestor;
  17. }
  18. public List<TreeNode> getPath(TreeNode root, TreeNode target) {
  19.     if (root == null || target == null) return null;
  20.     List<TreeNode> path = new ArrayList();
  21.     TreeNode curNode = root;
  22.     while ((curNode != null) && curNode.val != target.val) {
  23.         path.add(curNode);
  24.         if (curNode.val < target.val)    curNode = curNode.right;
  25.         else curNode = curNode.left;
  26.     }
  27.     path.add(curNode);
  28.     return path;
  29. }
  30. //一次遍历
  31. public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
  32.     if (root == null || p == null || q == null) return null;
  33.     TreeNode ancestor = root;
  34.     while (true) {
  35.         if (p.val < ancestor.val && q.val < ancestor.val) ancestor = ancestor.left;
  36.         else if (p.val > ancestor.val && q.val > ancestor.val) ancestor = ancestor.right;
  37.         else break;
  38.     }
  39.     return ancestor;
  40. }