【入门】lintcode 632: 二叉树的最大节点

在二叉树中寻找值最大的节点并返回。

样例

给出如下一棵二叉树：

     1
   /   \
 -5     2
 / \   /  \
0   3 -4  -5

返回值为 3 的节点。

当然是递归。

/**
 * Definition of TreeNode:
 * public class TreeNode {
 *     public int val;
 *     public TreeNode left, right;
 *     public TreeNode(int val) {
 *         this.val = val;
 *         this.left = this.right = null;
 *     }
 * }
 */
public class Solution {
    /*
     * @param root: the root of tree
     * @return: the max node
     */
    public TreeNode maxNode(TreeNode root) {
        // write your code here
        if(root == null)
            return null;
        
        TreeNode max = new TreeNode(root.val);
            
        if(root.left != null){
            TreeNode leftMaxNode = maxNode(root.left);
            max = max.val > leftMaxNode.val ? max : leftMaxNode;
        }
            
        if(root.right != null){
            TreeNode rightMaxNode = maxNode(root.right);
            max = max.val > rightMaxNode.val ? max : rightMaxNode;
        }
            
        return max;

    }
}

方法二：

/**
 * Definition of TreeNode:
 * public class TreeNode {
 *     public int val;
 *     public TreeNode left, right;
 *     public TreeNode(int val) {
 *         this.val = val;
 *         this.left = this.right = null;
 *     }
 * }
 */
public class Solution {
    /*
     * @param root: the root of tree
     * @return: the max node
     */
    public TreeNode maxNode(TreeNode root) {
        // write your code here
        if(root == null)
            return null;
        
        TreeNode leftMaxNode = maxNode(root.left);
        TreeNode rightMaxNode = maxNode(root.right);
        
        return max(root , max(leftMaxNode,rightMaxNode));
    }
    
    private TreeNode max(TreeNode node1 , TreeNode node2){
        if(node1 == null)
            return node2;
        if(node2 == null)
            return node1;
        if(node1.val > node2.val)
            return node1;
        else
            return node2;
    }
}