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

image.png
思路：关键点:

  • 左右子树各有其中一个已知节点；如果一个节点的左子树没有两个节点的任意一个，那么祖先肯定在其右子树上。

  • 如果在遍历过程中，当前遍历的节点是其中一个移植节点，那当前结点就是公共祖先的候选人。

    1. class Solution {
    2.   public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
    3.       if (root == p || root == q) return root;//找到公共祖先候选人
    4.       if (root == null) return null;
    5.       TreeNode left = lowestCommonAncestor(root.left, p, q);
    6.       TreeNode right = lowestCommonAncestor(root.right, p, q);
    8.       if (left != null && right != null) return root;
    9.       return left != null ? left : right;
    10.   }
    11. }

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

    image.png

    1. class Solution {
    2.   public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
    3.       if (root == null) return root;
    4.       if (root.val > p.val && root.val > q.val) {
    5.           return lowestCommonAncestor(root.left, p, q);
    6.       } else if (root.val < p.val && root.val < q.val) {
    7.           return lowestCommonAncestor(root.right, p, q);
    8.       }
    9.       return root;
    10.   }
    11. }

    99. 恢复二叉搜索树

    image.png
    2,3,4,5,6,7,8
    2,3, 7,5, 6,4, 8
    思路：二叉搜索树在中序遍历后是有序的，如果两个节点交换后，那么就会出现两个逆序对，如果是两个相邻的节点互换，那么只会出现一个逆序对，中序遍历时，如果出现逆序对，第一个逆序对的前一个是目标元素之一，第二个逆序对的后一个元素是另一个目标元素，找到两个元素后交换一下就ok了。

    1. class Solution {
    2.   TreeNode first = null;
    3.   TreeNode second = null;
    4.   TreeNode prev;
    5.   public void recoverTree(TreeNode root) {
    6.       dfs(root);
    7.       int tmp = first.val;
    8.       first.val = second.val;
    9.       second.val = tmp;
    10.   }
    11.   private void dfs(TreeNode node) {
    12.       if (node == null) return;
    13.       dfs(node.left);
    14.       if (prev != null && node.val < prev.val) {
    15.           if (first == null) {
    16.               first = prev;
    17.           }
    18.           second = node;
    19.       }
    20.       prev = node;
    21.       dfs(node.right);
    22.   }
    23. }

    way2:使用Morris中序遍历，可以将空间复杂度降到O(1)

    1. class Solution {
    2.   TreeNode prev;
    3.   TreeNode first;
    4.   TreeNode second;
    5.   public void recoverTree(TreeNode root) {
    6.       if (root == null) return;
    7.       while (root != null) {
    8.           if (root.left != null) {
    9.               TreeNode preNode = root.left;
    10.               while (preNode.right != null && preNode.right != root) {
    11.                   preNode = preNode.right;
    12.               }
    13.               if (preNode.right == null) {
    14.                   preNode.right = root;
    15.                   root = root.left;
    16.               } else {
    17.                   find(root);
    18.                   preNode.right = null;
    19.                   root = root.right;
    20.               }
    21.           } else {
    22.               find(root);
    23.               root = root.right;
    24.           }
    25.       }
    26.       int tmp = first.val;
    27.       first.val = second.val;
    28.       second.val = tmp;
    29.   }
    30.   private void find(TreeNode node) {
    31.       if (prev != null && node.val < prev.val) {
    32.           if (first == null) {
    33.               first = prev;
    34.           }
    35.           second = node;
    36.       }
    37.       prev = node;
    38.   }
    39. }

    98. 验证二叉搜索树

    image.png
    方法一：一开始的思路，找到前驱节点和后继节点，分别判断大小，方法不好

    1. class Solution {
    2.   public boolean isValidBST(TreeNode root) {
    3.       if (root == null) return true;
    4.       TreeNode prev = findPredecessor(root);
    5.       TreeNode successor = findSuccessor(root);
    6.       if (prev != null && prev.val >= root.val) return false;
    7.       if (successor != null && root.val >= successor.val) return false;
    8.       return isValidBST(root.left) && isValidBST(root.right);
    9.   }
    10.   private TreeNode findPredecessor(TreeNode node) {
    11.       TreeNode predecessor = node.left;
    12.       while (predecessor != null && predecessor.right != null) {
    13.           predecessor = predecessor.right;
    14.       }
    15.       return predecessor;
    16.   }
    17.   private TreeNode findSuccessor(TreeNode node) {
    18.       TreeNode successor = node.right;
    19.       while (successor != null && successor.left != null) {
    20.           successor = successor.left;
    21.       }
    22.       return successor;
    23.   }
    24. }

    方法2：递归法，设定这棵树的最大值和最小值。要考虑节点的值是Integer的最大值和最小值。

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

    方法3:dfs

    1. class Solution {
    2.   private TreeNode prev = null; 
    3.   private boolean res = true;
    4.   public boolean isValidBST(TreeNode root) {
    5.       dfs(root);
    6.       return res;
    7.   }
    8.   private void dfs(TreeNode node) {
    9.       if (node == null) return;
    10.       if (res == false) return;
    11.       dfs(node.left);
    12.       if (prev != null && prev.val >= node.val) {
    13.           res = false;
    14.       }
    15.       prev = node;
    16.       dfs(node.right);
    17.   }
    18. }

    方法3：使用栈遍历

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

    333. 最大 BST 子树

    image.png
    思路：定义一个方法getInfo(TreeNode node)，返回以node为根节点的二叉树里最大BST的信息。

    1. class Solution {
    2.   public int largestBSTSubtree(TreeNode root) {
    3.       if (root == null) return 0;
    4.       return getInfo(root).size;
    5.   }
    6.   private Info getInfo(TreeNode node) {
    7.       if (node == null) return null;
    8.       Info li = getInfo(node.left);
    9.       Info ri = getInfo(node.right);
    10.       boolean lValid = (li == null) || (li.root == node.left && li.max < node.val);
    11.       boolean rValid = (ri == null) || (ri.root == node.right && ri.min > node.val);
    12.       if (lValid && rValid) {
    13.           Info info = new Info();
    14.           info.root = node;
    15.           info.max = ri == null ? node.val : ri.max;
    16.           info.min = li == null ? node.val : li.min;
    17.           info.size = (li == null ? 0 : li.size) + (ri == null ? 0 : ri.size) + 1;
    18.           return info;
    19.       }
    20.       if (li != null && ri != null) {
    21.           return li.size > ri.size ? li : ri;
    22.       }
    23.       return li != null ? li : ri;
    24.   }
    25.   class Info {
    26.       TreeNode root;
    27.       Integer max;
    28.       Integer min;
    29.       Integer size;
    30.   }
    31. }

    102. 二叉树的层序遍历

    image.png

    1. class Solution {
    2.   public List<List<Integer>> levelOrder(TreeNode root) {
    3.       List<List<Integer>> res = new LinkedList();
    4.       if (root == null) return res;
    5.       LinkedList<TreeNode> queue = new LinkedList();
    6.       queue.add(root);
    7.       while (!queue.isEmpty()) {
    8.           int size = queue.size();
    9.           List<Integer> level = new LinkedList();
    10.           while (size-- != 0) {
    11.               TreeNode node = queue.pollFirst();
    12.               level.add(node.val);
    13.               if (node.left != null) queue.add(node.left);
    14.               if (node.right != null) queue.add(node.right);
    15.           }
    16.           res.add(level);
    17.       }
    18.       return res;
    19.   }
    20. }

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

    image.png

    1. class Solution {
    2.   public TreeNode buildTree(int[] preorder, int[] inorder) {
    3.       return buildTree(preorder, 0, preorder.length - 1, inorder, 0, inorder.length - 1);
    4.   }
    5.   private TreeNode buildTree(int[] preorder, int i1, int j1, int[] inorder, int i2, int j2) {
    6.       if (i1 > j1) return null;
    7.       TreeNode root = new TreeNode(preorder[i1]);
    8.       int i = i2;
    9.       for (; i <= j2; i++) {
    10.           if (inorder[i] == preorder[i1]) break;
    11.       }
    12.       root.left = buildTree(preorder, i1 + 1, i1 + i - i2, inorder, i2, i - 1);
    13.       root.right = buildTree(preorder, i1 + i - i2 + 1, j1, inorder, i + 1, j2);
    14.       return root;
    15.   }
    16. }

    优化下：上面的代码每次在中序数组里寻找元素时都需要遍历，可以提前将数组对应的下标存放在一个map里

    1. class Solution {
    2.   Map<Integer,Integer> map = new HashMap();
    3.   public TreeNode buildTree(int[] preorder, int[] inorder) {
    4.       for (int i = 0; i < inorder.length; i++) {
    5.           map.put(inorder[i], i);
    6.       }
    7.       return buildTree(preorder, 0, preorder.length - 1, inorder, 0, inorder.length - 1);
    8.   }
    9.   private TreeNode buildTree(int[] preorder, int i1, int j1, int[] inorder, int i2, int j2) {
    10.       if (i1 > j1) return null;
    11.       TreeNode root = new TreeNode(preorder[i1]);
    12.       int i = map.get(preorder[i1]);
    13.       root.left = buildTree(preorder, i1 + 1, i1 + i - i2, inorder, i2, i - 1);
    14.       root.right = buildTree(preorder, i1 + i - i2 + 1, j1, inorder, i + 1, j2);
    15.       return root;
    16.   }
    17. }

    617. 合并二叉树

    image.png

    1. class Solution {
    2.   public TreeNode mergeTrees(TreeNode root1, TreeNode root2) {
    3.       if (root1 == null) return root2;
    4.       if (root2 == null) return root1;
    5.       TreeNode newNode = new TreeNode(root1.val + root2.val);
    6.       newNode.left = mergeTrees(root1.left, root2.left);
    7.       newNode.right = mergeTrees(root1.right, root2.right);
    8.       return newNode;
    9.   }
    10. }

    101. 对称二叉树

    image.png
    方法1：递归法

    1. class Solution {
    2.   public boolean isSymmetric(TreeNode root) {
    3.       return isSymmetric(root, root);
    4.   }
    5.   private boolean isSymmetric(TreeNode node1, TreeNode node2) {
    6.       if (node1 == null && node2 == null) return true;
    7.       if (node1 == null || node2 == null) return false;
    8.       return node1.val == node2.val && isSymmetric(node1.left, node2.right) && isSymmetric(node1.right, node2.left);
    9.   }
    10. }