[LeetCode]671. 二叉树中第二小的节点(递归)

题目

给定一个非空特殊的二叉树，每个节点都是正数，并且每个节点的子节点数量只能为 2 或 0。如果一个节点有两个子节点的话，那么这个节点的值不大于它的子节点的值。

给出这样的一个二叉树，你需要输出所有节点中的第二小的值。如果第二小的值不存在的话，输出 -1 。

题解

有趣的一道题。

题目变成找出子树中最小的大于根结点值的节点值，否则-1
要充分利用该树的子节点值一定>=根节点的信息。
具体思路在代码注释。

代码

class Solution {

    public int findSecondMinimumValue(TreeNode root) {

        return helper(root,root.val);

    }

    public int helper(TreeNode root,int minVal){

        //叶子端点

        if(root==null){

            return -1;

        }

        //如果当前结点值>根节点，那么不用再遍历它的子节点，直接返回该值

        if(root.val>minVal){

            return root.val;

        }

        //否则，即当前结点值==根节点,则需要在两棵子树找目标值结点

        int l=helper(root.left,minVal);

        int r=helper(root.right,minVal);

        //如果两棵子树均存在大于最小值的节点，那么返回较小的那一个

        if(l!=-1&&r!=-1){

            return Math.min(l,r);

        }else{//否则，其余情况均返回较大的那一个

            return Math.max(l,r);

        }

    }

}

巴特西

[LeetCode]671. 二叉树中第二小的节点(递归)

题目

题解

代码

最新文章

热门文章