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

怼烎@ 2024-02-18 20:24 5阅读 0赞

### 题目 ###

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

样例  
给出如下一棵二叉树：

1  
/ \\  
\-5 2  
/ \\ / \\  
0 3 -4 -5  
返回值为 3 的节点。

### 解答 ###

public class FindMaxNumInTree {
        
    
        public static void main(String[] args) {
            TreeNode treeNode1 = new TreeNode(1);
            TreeNode treeNode2 = new TreeNode(-5);
            TreeNode treeNode3 = new TreeNode(2);
            TreeNode treeNode4 = new TreeNode(0);
            TreeNode treeNode5 = new TreeNode(3);
            TreeNode treeNode6 = new TreeNode(-4);
            TreeNode treeNode7 = new TreeNode(5);
    
            treeNode1.left = treeNode2;
            treeNode1.right = treeNode3;
            treeNode2.left = treeNode4;
            treeNode2.right = treeNode5;
            treeNode3.left = treeNode6;
            treeNode3.right = treeNode7;
    
            System.out.println(maxNode(treeNode1).val);
    
        }
    
        /*
             * @param root: the root of tree
             * @return: the max node
             */
        public static TreeNode maxNode(TreeNode root) {
            // write your code here
            TreeNode treeNode = root;
            return  getMax(root, treeNode);
        }
    
        public static TreeNode getMax(TreeNode currentNode, TreeNode maxNode) {
            if (currentNode == null){
                return maxNode;
            }
            if (currentNode.val > maxNode.val) {
                maxNode = currentNode;
            }
            TreeNode leftTreeNode = getMax(currentNode.left, maxNode);
            TreeNode rightTreeNode = getMax(currentNode.right, maxNode);
            return leftTreeNode.val>rightTreeNode.val?leftTreeNode:rightTreeNode;
        }
    
        public static class TreeNode {
        
            public int      val;
            public TreeNode left, right;
    
            public TreeNode(int val) {
                this.val = val;
                this.left = this.right = null;
            }
        }
    }