LintCode(632)查找二叉树中值最大的节点

旧城等待， 2022-05-12 15:16 201阅读 0赞

问题

Find the maximum node in a binary tree, return the node.

Example

Given a binary tree:

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

return the node with value `3`.

考虑遍历二叉树来解决

java解答

/**
     * 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
         */
         /**
          * 思路
          * 1，参数合法性判断
          * 2，遍历二叉树，找出最大节点
          */
        public TreeNode maxNode(TreeNode root) {
            // write your code here
            if(root == null){
                return null;
            }
            //最大的节点
            TreeNode maxNode = root;
            //当前节点
            TreeNode p = root;
            //临时存放二叉树的链表集合
            LinkedList<TreeNode> nodeLink = new LinkedList<TreeNode>();
            while(p != null || !nodeLink.isEmpty()){
                if(p != null){
                    nodeLink.push(p);
                    p = p.left;
                }else{
                    p = nodeLink.pop();
                    if(maxNode.val < p.val){
                        maxNode = p;
                    }
                    p = p.right;
                }
            }
            return maxNode;
        }
    }