2018-04-18 二叉树取最大节点

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

给出如下一棵二叉树：

 
            a(1) 
           /      \
        b(-5)      c(2)
        /   \      /   \
     d(0) e(3)  f(-4)  g(-5) 
                   \
                   h(6)
                  /
                m(4)
     
     
返回值为 6 的节点。

代码如下:

package cn.jq.binarytree;

import java.util.ArrayList;

import cn.jq.binarytree.BinaryTree.Node;

public class SortBinaryTree {

    
    /**
     * 创建一颗整型二叉树, 
     *       a(1) 
     *     /      \
     *  b(-5)      c(2)
     *  /   \      /   \
     *d(0) e(3)  f(-4)  g(-5) 
     *              \
     *              h(6)
     *             /
     *           m(4)
     * @return
     */
    public static BinaryTree initBinaryTree() {
        Node m = new BinaryTree().new Node("4", null, null);
        Node h = new BinaryTree().new Node("6", m, null);
        Node g = new BinaryTree().new Node("-5", null, null);
        Node f = new BinaryTree().new Node("-4", null, h);
        Node e = new BinaryTree().new Node("3", null, null);
        Node d = new BinaryTree().new Node("0", null, null);
        Node c = new BinaryTree().new Node("2", f, g);
        Node b = new BinaryTree().new Node("-5", d, e);
        Node a = new BinaryTree().new Node("1", b, c);
        Node root = a; 
        return new BinaryTree(root);
    }
    
    public Node maxNode(Node root) {
        //Write your code here
        ArrayList<Node> result = new ArrayList<Node>();
        result.add(root);
        search(root, result);
        return result.get(0);
    }
    
    
    //递归查询最大节点
    public void search(Node root, ArrayList<Node> result) {
        if (root == null) {
            return ;
        }
        if (Integer.valueOf(result.get(0).getData()) < Integer.valueOf(root.getData())) {
            result.set(0, root);
        }
        if (root.getLchild() != null) {
            search(root.getLchild(), result);
        }
        if (root.getRchild() != null) {
            search(root.getRchild(), result);
        }
    }
    
    
    public static void main(String args[]) {
        BinaryTree tree = SortBinaryTree.initBinaryTree();
        SortBinaryTree sortBinary = new SortBinaryTree();
        System.out.println(sortBinary.maxNode(tree.getRoot()).getData());
    }
}