【树】关于树的遍历相关变种题目

一、前序遍历相关

二、中序遍历相关

题解报告LeetCode#230：二叉搜索树中第 K 小的元素

题意：LeetCode#230：二叉搜索树中第 K 小的元素

思路：中序遍历一套带走

代码：

class Solution {
    int count, res;
    public int kthSmallest(TreeNode root, int k) {
        if (root.left != null) kthSmallest(root.left, k);
        if (++count == k) res = root.val; // 注意不能在这里返回 // 妈的，可以在这里返回    
        if (root.right != null) kthSmallest(root.right, k);
        return res;
    }
}

题解报告LeetCode#530：二叉搜索树的最小绝对差

题意：LeetCode#530：二叉搜索树的最小绝对差

思路：中序遍历一波带走

代码：

class Solution {
    private int result = Integer.MAX_VALUE;
    private TreeNode preNode = null;
    public int getMinimumDifference(TreeNode root) {
        getMin(root);
        return result;
    }
    private void getMin(TreeNode root) {
        if (root == null) {
            return;
        }
        getMin(root.left);
        if (preNode != null) {
            result = Math.min(Math.abs(root.val - preNode.val), result);
        }
        preNode = root;
        getMin(root.right);
    }
}

题解报告LeetCode#1382：将二叉搜索树变平衡

题意：LeetCode#1382：将二叉搜索树变平衡

思路：

• 中序遍历（递归实现就可以了）
• 然后根据一个有序数组构造二叉搜索树

代码：

class Solution {
    public TreeNode balanceBST(TreeNode root) {
        List<Integer> nodes = new LinkedList<>();
        inOrder(nodes, root);
        int len = nodes.size();
        return buildBalanceBST(nodes, 0, len - 1);
    }
    private TreeNode buildBalanceBST(List<Integer> list, int start, int end) {
        if (start > end) {
            return null;
        }
        if (start == end) {
            return new TreeNode(list.get(start));
        }
        int mid = start + (start - end) / 2;
        TreeNode root = new TreeNode(list.get(mid));
        root.left = buildBalanceBST(list, start, mid -  1);
        root.right = buildBalanceBST(list, mid + 1, end);
        return root;
    }
    private void inOrder(List<Integer> list, TreeNode root) {
        // 递归一般还是采用这种直接将终止条件写出来的写法，比较能过脑
        if (root == null) {
            return;
        }
        inOrder(list, root.left);
        list.add(root.val);
        inOrder(list, root.right);
    }
}

三、后序遍历相关

题解报告LeetCode#104：二叉树的最大深度

题意：LeetCode#104：二叉树的最大深度

思路：后序遍历

代码：

class Solution {
    public int maxDepth(TreeNode root) {    
        return root == null ? 0 : Math.max(maxDepth(root.right), maxDepth(root.left)) + 1;
    }
}

题解报告LeetCode#111：二叉树的最小深度

题意：LeetCode#111：二叉树的最小深度

思路：后序遍历，但是要注意，但左节点不为空，右节点为空，不能直接拿左节点来当作最小深度来 + 1，同理右节点。

代码：

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

题解报告LeetCode#236：二叉树的最近公共祖先

题意：LeetCode#236：二叉树的最近公共祖先

思路：

• 由于“最近公共祖先”的定义，它是一个向上传的过程，先知道了左右子树遍历的结果，然后自己才能操作，这是“后序遍历”；
• 如果 p 和 q 都非空，返回它们的公共祖先；
• 如果只存在一个；
• 如果 p 和 q 都不存在，则返回空。

代码：

public class Solution {
      public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if (root == null || root == p || root == q) {
            return root;
        }
        TreeNode left = lowestCommonAncestor(root.left, p, q);
        TreeNode right = lowestCommonAncestor(root.right, p, q);
        // 下面两行代码不可能同时为空，因为题目保证 p 和 q 一定存在
        if (left == null) return right;
        if (right == null) return left;
        if (left != null && right != null) {
            return root;
        }
        return null;
    }
}

三、层序遍历相关