LeetCode中二叉树相关的算法题整理

本文以LeetCode中的二叉树相关的题目为依据，整理了一些对二叉树的常见操作。注：所有代码来自互联网。

判断两个树是否相同(100)

DFS

先想一下什么样的节点算是相同的，值相同以及左右孩子都相同，然后依次递归两个孩子节点，所以很容易想到这个深度优先的实现。然后想一下如何退出，如果不满足相同则可以立即退出，所以对比判断要在递归之前。最后要注意null的判断，即两个树的形状不相同的时候也是可以立刻判断并返回结果的。时间复杂度O(logn)，或者为树的高度h。

/**
 * Recursive, pre-order check
 * If both node''s values are the same, left subtrees are same and so right
 * Return true, otherwise return false
 */
public static boolean isSameTree(TreeNode p, TreeNode q) {
    // if one of them is null, it will return false. both null, true.
    if (p == null || q == null) return p == q; 
    // equal val, equal subtrees
    // 注意比较次数随着层级的加深而次数加多，整体呈放射状，但仍需要将每一层的所有方法进行与操作，e.g. map-reduce
    return p.val == q.val && isSameTree(p.left, q.left) && isSameTree(p.right, q.right); 
}

这道题是求是否的问题，并不是计算数值如和的问题，所以用递归求解有一点性能问题，尤其是在发现结果不满足后还需层层向上返回结果，如果层级较深，则有不少的内存消耗，性能也不高。

另外一个注意的点是，方法内部判断的顺序问题，因为当不满足条件时可以直接返回结果，不需要依赖下一层级的计算结果，所以需要将递归方法放到后面执行，可以减少可能的计算开销。

迭代

迭代的好处是如果发现条件不满足可以直接返回，适合这种求是否的二叉树问题，提高计算效率。另外使用队列的方式对于求两个树之间的相似问题是常用手段。

public boolean isSameTree(TreeNode p, TreeNode q) {
    // 使用队列的先进先出功能来处理二叉树是一个典型的思路
    Queue<TreeNode> queue = new LinkedList<>();
    queue.add(p);
    queue.add(q);
    while (!queue.isEmpty()) {
        TreeNode t1 = queue.poll();
        TreeNode t2 = queue.poll();
        if (t1 == null && t2 == null) continue;
        if (t1 == null || t2 == null) return false;
        if (t1.val != t2.val) return false;
        // 为下一轮迭代做准备，依次入队两个左孩子和两个右孩子
        // 左孩子
        queue.add(t1.left);
        queue.add(t2.left);
        // 右孩子
        queue.add(t1.right);
        queue.add(t2.right);
    }
    return true;
}

使用队列的思路是，每次循环只处理当前层的逻辑，下一层的逻辑（注意包括左右两个维度）交给队列下一次出队的时候再处理，并且每次只处理一个节点的逻辑，而不是同时处理左右孩子的出栈逻辑。所以递归的深度*逻辑的次数即为迭代方式的时间复杂度，即O(n)，每一个节点计算一次。

判断对称树(101)

对称和相同的唯一区别就是对比的树的节点是相对于树根是排列是「对称的」，即按照树根的垂直线进行合并后可以变成一半且每个节点都有重叠。

DFS

public boolean isSymmetric(TreeNode root) {
    return isMirror(root, root); // 拆分为两个树进行对比
}

public boolean isMirror(TreeNode t1, TreeNode t2) {
    if (t1 == null || t2 == null) return t1 == t2;
    return (t1.val == t2.val)
        && isMirror(t1.right, t2.left)
        && isMirror(t1.left, t2.right);
}

可以找一个满二叉树的图进行观测，你会发现只要left和right的关系确定下来，无论到哪一个层级都是符合这个规律的。

迭代方式

public boolean isSymmetric(TreeNode root) {
    // 使用队列的先进先出功能来处理二叉树是一个典型的思路
    Queue<TreeNode> q = new LinkedList<>();
    q.add(root);
    q.add(root);
    while (!q.isEmpty()) {
        TreeNode t1 = q.poll();
        TreeNode t2 = q.poll();
        if (t1 == null && t2 == null) continue;
        if (t1 == null || t2 == null) return false;
        if (t1.val != t2.val) return false;
        // 为下一轮迭代做准备，依次入队两个左孩子和两个右孩子
        // 左孩子和对方的右孩子
        q.add(t1.left);
        q.add(t2.right);
        // 右孩子和对方的左孩子
        q.add(t1.right);
        q.add(t2.left);
    }
    return true;
}

二叉树最大深度(104)

DFS

先想一下本层的深度怎么计算，左右孩子的最大深度加上1，根节点的深度是最大的，所以需要计算到叶子节点才能拿到结果，所以这里就需要先迭代计算依次拿到值往上层返回并最终拿到结果。就是本层的高度，时间复杂度为O(logn)。

private int maxDepth(TreeNode root) {
    if (root == null) {
        return 0;
    }
    int left = maxDepth(root.left);
    int right = maxDepth(root.right);
    return Math.max(left, right) + 1;
}

因为需要得到树的高度，所以依赖下一层的结果，所以递归方法需要放到前部，另外这类可以从树根到树叶一次性遍历后计算出结果的问题，使用递归比较简单。

最长唯一路径(687)

乍一看跟最大深度这道题差不多，但其实没有意识到一个问题就是路径并不一定是从父节点到子节点的，也可能是从子节点到父节点再到子节点。

所以区别就是深度是只要加上左右孩子的深度中大的一个再加上本层即可，而这里是需要加上左右两边最大的「有效值」再加上本parent节点1。

注意时间复杂度为O(h)，h=logn，即O(logn)，最坏情况下h=n，即O(n)。

public class LongestPurePath {

    int maxLen = 0;
    public int findPath(TreeNode root) {
        if(root == null){
            return 0;
        }
        getPath(root);
        return maxLen;
    }
    
    //获取左右子树中最长的路径值
    public int getPath(TreeNode root) {
        if(root == null){
            return 0;
        }
        //记录本节点的左右子树的最大路径长度
        int left = 0;
        int right = 0;
        // 注意只要存在子节点，则需要计算子节点中的最大路径长度，否则可能会计算不准
        if(root.left!=null){
            int len = getPath(root.left); //左子树的最大纯色值
            if(root.val == root.left.val){ // 注意，只有颜色相同时left才有意义否则为0
                left = len;
            }
        }
        if(root.right!=null){
            int len = getPath(root.right); // 右子树的最大纯色值
            if(root.val == root.right.val){ // 注意，只有颜色相同时right才有意义否则为0
                right = len;
            }
        }
        // 记录最大纯色值，注意包含本节点在内的左右路径中最大值的计算：左子树纯色值+当前节点1+右子树最大纯色值
        maxLen = Math.max(maxLen, left+right+1);
        // 向上层返回左右子树中最长的纯色值和本层的值，因为上层只可能用子节点到叶节点方向的一个分支的最大值
        // 前提是当前节点的左右子节点有一个跟它同色，否则left和right都是0，当前层的值为1
        return Math.max(left, right) + 1; 
    }
}

这道题和求最大高度的题本质上都是一样的，后者逻辑简单一点，但是流程都是递归，都是递归到叶子节点开始计算，并返回上层相应的结果进行计算。区别是这道题需要在本层返回之前单独计算全局的结果，而上一道题则不需要，递归的方法结果就是最终的结果。

判断是否为平衡树

需要知道任意层的节点的左右孩子的高度，然后计算是否符合绝对差不大于1，既然是高度就一定要算到叶子节点，所以采用递归的方式，好处是从底部获取高度的同时就可以计算是否符合条件进而快速获取到结果了。这样难免在靠近叶子节点的层级发现不符合条件时时还需要完成层层出栈的操作，极端情况下效率比较差。但是如果采用迭代的方式，从根依次往下计算每一个孩子的高度又会存在重复计算的问题，即每次都要计算。

private boolean isBalancedTree(TreeNode root) {
    return maxDepth(root) != -1;
}

private int maxDepth(TreeNode root) {
    if (root == null) {
        return 0;
    }
    // 先递归并获取本层的计算参数
    int left = maxDepth(root.left);
    int right = maxDepth(root.right);
    // 如果左侧或右侧已经不满足条件 或者 当前的左侧和右侧的差不满足条件，则返回-1
    if (left == -1 || right == -1 || Math.abs(left - right) > 1) 
        return -1;
    return Math.max(left, right) + 1; // 计算当前层的高度为下一层的高度+1
}

上面的算法充分利用了求树高度时可以计算二叉树是否是平衡二叉树的特性，避免了从顶部逐步向下依次计算每一个节点的左右子树的高进行对比导致的重复计算问题。

该题目和上面的 最长单色路径 是一样的思路，即需要求长度相关的一定要递归到树叶才能计算整体的结果，既然计算到了树叶就要避免多次计算过程，此时应该使用计算的每一次结果进行对目标的计算和保存，充分利用递归从底部往顶部出栈的过程完成计算，最终一次性得到结果，避免多次入栈出栈操作。

左叶子节点的和

DFS1

采用递归的方式处理，每一层的数值为左右子树中「左叶子节点」的数值之和，退出条件为 root == null ，此时返回 0 。注意由于父节点一定不满足条件，所以递归的结果就是左右之和，与当前父节点无关。

/**
 * DFS. Recursive.
 * Recurrence relation:
 * Sum of left leaves at root =
 * sum of left subtree''s left leaves + sum to right subtree''s left leaves
 * Left child can be a leaf or a subtree
 * Add its value to result.
 * Then call sum recursively on right subtree.
 * Base case:
 * If root is null, return 0.
 */
public int sumOfLeftLeaves(TreeNode root) {
    if (root == null) {
        return 0; // default value is 0
    }
    int sum = 0; // local variable
    
    // root.left is a leaf
    if (root.left != null && root.left.left == null && root.left.right == null) { 
        sum += root.left.val; // Add directly
    } else { // root.left is a subtree, recurse
        sum += sumOfLeftLeaves(root.left);
    }
    sum += sumOfLeftLeaves(root.right);
    return sum;
}

DFS2

通过一个布尔变量来标记当前的节点是左还是右，用于在需要统计叶子数值时做判断是加当前值还是加 0 ，然后递归执行。

/**
 * DFS. Recursive.
 * Pass another boolean to indicate whether the tree node is a left child
 */
public int sumOfLeftLeaves(TreeNode root) { 
    return dfs(root, false);
}

/**
 * DFS.
 * Base case:
 * 1) root is null, return 0.
 * 2) If current node is a leaf, and it''s from left, return its value.
 * The result is the sum of left leaves sum of left subtree and right subtree.
 */
private int dfs(TreeNode root, boolean isLeft) {
    if (root == null) {
        return 0;
    }
    // is leaf
    if (root.left == null && root.right == null) {
        return isLeft ? root.val : 0; // only left leaf counts
    }
    return dfs(root.left, true) + dfs(root.right, false);
}

前序遍历

使用 Stack 的先进后出功能来完成对二叉树的遍历是一种常用的方式，一般采用 前序遍历 的方式，注意入栈顺序，先处理右孩子，再处理左孩子。默认先压入 root ，再在每一轮循环后判断 Stack 是否为空。

/**
 * Stack, pre-order traversal
 * For each node, check if its left child is leaf
 * If so, add the value of that node to sum
 * Recurse on the left and right child
 */
public int sumOfLeftLeaves(TreeNode root) {
    if (root == null) {
        return 0;
    }
    final Stack<TreeNode> stack = new Stack<>();
    stack.push(root);
    int sum = 0; // Avoid overflow with long? sum should be within integer range.
    boolean isCounted;
    
    // pop once, push twice at most
    while (!stack.isEmpty()) {
        isCounted = false;
        TreeNode node = stack.pop();
        if (node.right != null) {
            stack.push(node.right); // right node's logic is simple, just push it into stack
        }
        if (node.left != null) {
            if (node.left.left == null && node.left.right == null) {
                sum += node.left.val;
                isCounted = true;
            }
            if (!isCounted) {
                stack.push(node.left);
            }
        }
    }
    return sum;
}

注意观察迭代版本和上面递归版本的区别，并分析迭代是怎样把递归中应该分散在两个嵌套调用的逻辑，合并到一次执行中的。

层次遍历

层次遍历或广度优先遍历，同样需要使用 Queue 数据结构，和使用 Stack 的思路差不多，但是顺序是先处理左孩子，再处理右孩子。

/**
 * Level-order traversal or BFS.
 */
public int sumOfLeftLeaves(TreeNode root) {
    if (root == null) {
        return 0;
    }
    int sum = 0;
    Queue<TreeNode> queue = new ArrayDeque<>();
    queue.offer(root); // enqueue root
    boolean isCounted;
    while (!queue.isEmpty()) {
        TreeNode node = queue.poll();
        if (node.left != null) {
            if (node.left.left == null && node.left.right == null) {
                sum += node.left.val;
                isCounted = true;
            }
            if(!isCounted) {
                queue.offer(node.left);
            }
        }
        if (node.right != null) {
            queue.offer(node.right);
        }
    }
    return sum;
}

二叉树路径(257)

回溯法

public List<String> binaryTreePaths(TreeNode root) {
    List<String> paths = new ArrayList<>();
    backtrack(root, new StringBuilder(), paths);
    return paths;
}

private void backtrack(TreeNode root, StringBuilder path, List<String> paths) {
    if (root == null) return;
    if (root.left == null && root.right == null) { // A leaf.
        paths.add(path.append(root.val).toString()); // find one, add to result list
        return;
    }
    path.append(root.val).append("->"); // Arrow should be appended before reaching leaf.
    int len = path.length();
    backtrack(root.left, path, paths);
    path.setLength(len); // Reset path.
    backtrack(root.right, path, paths);
    path.setLength(len);
}

二叉树的最小的公共祖先(236)

因为这是一颗普通的二叉树，所以父节点和左右孩子节点之间没有数值上的关系，如果要找到父节点，只能先找到对应的两个节点p和q，所以需要从树根开始依次从左右两侧开始寻找，如果找到则返回，交给上一层处理，上一层只负责将左右两侧的结果向上返回，如果左边找到了右边没找到则当前节点不是要找的祖先，则继续往上层返回找到的节点，如果右边找到了也是类似的逻辑，如果左右两边都找到了，则返回当前节点。此时其他分支是不可能找到结果的，最终将返回null，回溯到根节点时将返回找到的层层上传的那个节点。

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); // 从右边继续寻找
    // 如果左边没找到，则返回右边的结果
    // 如果左边找到了，右边没找到，返回左边即可，此时另外一个节点是左边的值的孩子节点
    // 如果左边右边各找到一个节点，则返回父节点
    return left == null ? right : (right == null ? left : root);
}

二叉搜索树的最小的公共祖先(235)

与上一题的区别在于，二叉搜索树是满足left<parent<right的，所以可以通过value比对的区间情况进行对符合条件的parent的寻找，由于判断条件只与本层当前节点和目标两个节点之间的大小关系有关，所以从树根开始依次向下进行判断即可，使用迭代的方式。

注意大于left并且小于right的节点并不一定是公共祖先，比如可能和left是同一层的节点，所以从树根开始寻找时找到第一个符合条件的节点就是最小的节点。

如随便搜了一张图：可知，如果left是1，right是7，那么6是符合条件在二者之间的，但是它并不是公共父节点，而应该是3，如果从树根开始依次判断，则会在计算3的时候得出答案。

public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
    while (root != null) {
        // root比两个点都小，则往大里继续找，即右子树方向
        if (root.val < p.val && root.val < q.val) {
            root = root.right;
        } else if (root.val > p.val && root.val > q.val) {
            // root比两个点都大，则往小里继续找，即左子树方向
            root = root.left;
        } else {
            // 否则root在p和q之间，即为二者的parent，也是最小也是唯一的，直接返回
            return root;
        }
    }
    return null; // Reach null and lca not found.
}

验证二叉搜索树(98)

DFS

二叉搜索树的特点是，父节点大于左孩子中的最大的值小于右孩子中最小的值，每一个节点都要满足，如果不满足可以快速退出。因为该特性一定涉及到判断最左侧叶子节点或最右侧的椰子节点和当前节点的关系，每一层都需要判断，所以可以使用递归来完成左孩子和右孩子的计算。流程是：从头结点开始判断是否符合其「左子树中的最大的值」小于该节点的值，「右子树中最小的值」大于该节点的值，然后依次判断该节点的左右孩子节点。一旦不满足则返回false，不再计算。

public boolean isValidBST(TreeNode root) {
    if (root == null) { // 默认返回true
        return true;
    }
    TreeNode temp = null;
    if (root.left != null) {
        temp = root.left; // 左孩子
        // 找到左孩子下面的最大值，即一直遍历右孩子，保证其要小于root
        while (temp.right != null) {
            temp = temp.right;
        }
        // 如果大于root，则返回false
        if (temp.val >= root.val) {
            return false;
        }
    }
    if (root.right != null) {
        temp = root.right; // 右孩子
        // 找到右孩子下面的最小值，保证其要大于root
        while (temp.left != null) {
            temp = temp.left;
        }
        // 如果小于root，则返回false
        if (temp.val <= root.val) {
            return false;
        }
    }
    // 递归判断左孩子和右孩子
    return isValidBST(root.left) && isValidBST(root.right);
}

层次遍历(102)

Queue

使用FIFO队列完成每一层数据的按顺序入队，在完成每一层队列出队的同时完成下一层次数据的入队，由于使用同一个队列，需使用序号来限制每一轮中只出队本层次的节点。该长度由本轮开始时当前队列的长度决定。

private List<List<Integer>> levelOrder(TreeNode root) {
    if (root == null) {
        return Collections.EMPTY_LIST;
    }
    Queue<TreeNode> queue = new ArrayDeque<>();
    queue.offer(root);
    List<List<Integer>> levels = new ArrayList<>();
    while (!queue.isEmpty()) {
        List<Integer> values = new ArrayList<>();
        // 分别处理每一层的节点数，由queue.size()控制
        for (int i = queue.size(); i > 0; i--) {
            TreeNode n = queue.poll();
            values.add(n.val); // Add current node''s value to current level''s values list.
            if (n.left != null) {
                queue.add(n.left);
            }
            if (n.right != null) {
                queue.add(n.right);
            }
        }
        levels.add(values);
    }
    return levels;
}

DFS

public List<List<Integer>> levelOrder2(TreeNode root) {
    List<List<Integer>> res = new ArrayList<>();
    dfs(root, 0, res);
    return res;
}

/**
 * Like pre-order traversal.
 * Visit current node.
 * Add current node''s value to its corresponding level.
 * If the level doesn''t exist, add an empty list first.
 * Then visit left node.
 * Then visit right node.
 */
public void dfs(TreeNode root, int level, List<List<Integer>> res) {
    if (root == null) {
        return;
    }
    if (res.size() <= level) {
        res.add(new ArrayList<>()); // init current level's List
    }
    res.get(level).add(root.val); // add current node to current level's list
    dfs(root.left, level + 1, res); // left first
    dfs(root.right, level + 1, res); // right second
}

二叉搜索树迭代器(173)

要求：迭代器每次需要返回剩余数据的最小值，next和hasNext的时间复杂度为O(1)，空间复杂度为O(h)，h为树的高度。

由于是二叉搜索树，可以使用堆栈数据结构，每次最多使用数高的长度的数组来存储，以实现O(h)的空间复杂度，然后在处理数据的时候，继续入队其他节点的数据，依旧满足O(h)的空间复杂度。

Deque<TreeNode> stack;

/**
 * Simulate in-order traversal.
 * Push all left children into a Stack to get prepared.
 */
public BinarySearchTreeIterator(TreeNode root) {
    stack = new ArrayDeque<>();
    // 初始化时将root和它的全部左孩子按顺序依次加入到堆栈中，注意此时不一定满足存储了h个元素，需要看树的结构
    pushAllLeft(root); 
}

/**
 * If the stack is empty, there is no more node left.
 */
public boolean hasNext() {
    return !stack.isEmpty();
}

/**
 * Imagine all left subtree of a node is popped out.
 * The next will be itself.
 * And then the next will be its right subtree.
 * The right subtree repeats the pattern of pushing all left children into a stack.
 */
public int next() {
    TreeNode n = stack.pop(); // 每次出栈当前最小的值
    pushAllLeft(n.right); // Left subtree and root is done. Repeat on right subtree.
    return n.val;
}

private void pushAllLeft(TreeNode root) {
    while (root != null) {
        stack.push(root);
        root = root.left;
    }
}

二叉树右侧视角集合(199)

public List<Integer> rightSideView(TreeNode root) {
    Map<Integer, Integer> rightmostValueAtDepth = new HashMap<Integer, Integer>();
    int max_depth = -1;

    /* These two Queues are always synchronized, providing an implicit
     * association values with the same offset on each Queue. */
    Queue<TreeNode> nodeQueue = new LinkedList<TreeNode>();
    Queue<Integer> depthQueue = new LinkedList<Integer>();
    nodeQueue.add(root);
    depthQueue.add(0);

    while (!nodeQueue.isEmpty()) {
        TreeNode node = nodeQueue.remove();
        int depth = depthQueue.remove();

        if (node != null) {
            max_depth = Math.max(max_depth, depth);

            /* The last node that we encounter at a particular depth contains
            * the correct value, so the correct value is never overwritten. */
            // 每次都覆盖同一层的最右数据的值，因为最后处理的一定是最大的，所以这里覆盖不影响最终结果
            rightmostValueAtDepth.put(depth, node.val);

            // 将左右孩子加到队尾
            nodeQueue.add(node.left);
            nodeQueue.add(node.right);
            // 保持和节点队列的一致性
            depthQueue.add(depth + 1);
            depthQueue.add(depth + 1);
        }
    }

    /* Construct the solution based on the values that we end up with at the
     * end. */
    List<Integer> rightView = new ArrayList<Integer>();
    for (int depth = 0; depth <= max_depth; depth++) {
        rightView.add(rightmostValueAtDepth.get(depth));
    }

    return rightView;
}

反转二叉树(226)

一个节点只需要将它的左右节点的指向进行反转即可，并依次向上继续反转操作，所以要使用递归，从底部到顶部进行处理。

退出条件是节点为null时直接返回null即可，即不反转。其他情况，完成左右孩子的反转后返回当前节点。

public TreeNode invertTree(TreeNode root) {
    if (root == null) {
        return null;
    }
    // 分别将左右节点进行反转，递归
    TreeNode right = invertTree(root.right);
    TreeNode left = invertTree(root.left);
    // 重新设置当前节点的左右孩子的指向，完成反转
    root.left = right;
    root.right = left;
    return root;
}

二叉搜索树中的第K小的值

因为搜索树是中序遍历有序的，所以利用这个规则可以找到最小的节点，并依次向上判断直到该节点是第K小的。

迭代

利用堆栈先进后出的特性，将所有左孩子依次压入栈，直到为叶子节点位置，处理相应的逻辑后，继续从该节点的右孩子开始继续将所有左孩子压入栈，没有则继续弹出栈顶元素，因为每次弹出栈顶元素都是当前的最小值，除非不需要弹，当前节点仍然有左孩子则继续压入栈，因为这个节点的值更小。最后如果堆栈空了并且也没有节点可以压入栈了，则退出迭代。

public int kthSmallest(TreeNode root, int k) {
    Deque<TreeNode> stack = new ArrayDeque<>();
    int count = k;
    // 注意条件满足栈不为空或root不为null即可
    while (!stack.isEmpty() || root != null) {
        // 保证节点不为null
        if (root != null) { // 先将所有左孩子节点放入堆栈
            stack.push(root);
            root = root.left;
        } else {
            // 直到没有左孩子，弹出栈顶元素，此为当前最小元素
            root = stack.pop(); // 出队左孩子
            count--; // 标记倒数第几个最小值
            if (count == 0) {
                return root.val;
            }
            root = root.right; // 从该节点右孩子开始继续处理
        }
    }
    // 没找到
    return -1;
}

递归

只需要保证当前节点和它的所有孩子节点的个数和k相同即找到了对应的解，返回该节点的最大的右孩子的值即可。而该问题又可以变化为小问题，即如果节点的左侧节点（都小于该节点）的数目+1小于要找的K值，则从该节点的右孩子开始寻找第k-1-sum(左侧节点个数)个小的节点即可。即K在大问题每次变化为小问题后都会是原K值-1-原节点的左侧孩子个数。

public int kthSmallest(TreeNode root, int k) {
    // 先统计当前节点的左侧节点的个数，递归一直到左侧叶子节点
    int count = countNodes(root.left);
    // 如果k小于count，则只需要在左侧寻找
    if (k < count) {
        return kthSmallest(root.left, k); 
    } else if (k > count + 1) {
        // 否则在当前节点右侧寻找
        // 注意因为在右侧寻找时，左侧一定寻找完毕，所以要把左侧的减去并且默认跳过了当前节点所以要多减去一
        return kthSmallest(root.right, k - 1 - count); // 1 is counted as current node
    }
    // 如果k恰好等于count则返回当前节点的值
    return root.val;
}
// 递归寻找某个节点为根的树的包含节点的个数
private int countNodes(TreeNode n) {
    if (n == null) {
        return 0;
    }
    return 1 + countNodes(n.left) + countNodes(n.right);
}

统计相同值子树的个数(250)

默认叶子节点是一颗相同值子树，符合条件；其他情况均需要满足父节点和左孩子（如果有）、右孩子（如果有）所有的节点的值都相同才叫子树。所以还是要从叶子节点开始计算，所以要先递归，并将结果返回上层进行计算，一旦出现不满足直接返回，如果满足则计数并依次返回上一层继续计算。

public int countUnivalSubtrees(TreeNode root) {
    int[] count = new int[1]; // reference
    helper(root, count);
    return count[0];
}

private boolean helper(TreeNode node, int[] count) {
    if (node == null) { // 默认是true
        return true;
    }
    boolean left = helper(node.left, count);
    boolean right = helper(node.right, count);
    if (left && right) {
        // 有左孩子，要保证和父节点值相同
        if (node.left != null && node.val != node.left.val) {
            return false;
        }
        // 有右孩子，要保证和父节点值相同
        if (node.right != null && node.val != node.right.val) {
            return false;
        }
        count[0]++; // 无左右孩子（叶子）或者和左右孩子都相同则计数+1
        return true;
    }
    // 一旦left或right返回的是false则本层和上层都不可能是相同的子树了，所以直接返回
    return false;
}

References

https://leetcode.com

本文首次发布于 LiuShuo’s Blog, 转载请保留原文链接.

Binary Tree Algorithms in LeetCode