二叉树求最短路径

痛定思痛。 2022-06-14 10:22 175阅读 0赞

#include<iostream>
    #include<stdlib.h>
    using namespace std;
    template <class T>
    struct BinaryTreeNode
    {
        BinaryTreeNode(const T& data)
        :_data(data)
        , _left(NULL)
        , _right(NULL)
        {
    
        }
        BinaryTreeNode<T>*_left;
        BinaryTreeNode<T>*_right;
        T _data;
    };
    template<class T>
    class BinaryTree
    {
    public:
        typedef BinaryTreeNode<T> Node;
        BinaryTree()
            :_root(NULL)
        {
    
        }
        Node* _root;
        BinaryTree(T*arr, int size, int invalid)
        {
            int index = 0;
            _root = _CreateBinaryTree(_root, arr, size, index,invalid);
        }
        int ShortDepth()
        {
            if (!_root)
            {
                return 0;
            }
            int depth = 0;
            return _ShortDepth(_root, depth);
        }
    protected:
        Node* _CreateBinaryTree(Node*root, T*arr, int size, int &index,int invalid)
        {
            root = NULL;
            if (index < size&&arr[index] != invalid)
            {
                Node*NewNode = new Node(arr[index]);
                root = NewNode;
                root->_left=_CreateBinaryTree(root->_left, arr, size,++index, invalid);
                root->_right=_CreateBinaryTree(root->_right, arr, size, ++index, invalid);
            }
            return root;
        }
        int _ShortDepth(Node*root, int depth)
        {
            int minLeft = -1;
            int minRight = -1;
            if (root->_left)
            {
                minLeft = _ShortDepth(root->_left, depth + 1);
            }
            if (root->_right)
            {
                minRight = _ShortDepth(root->_right, depth + 1);
            }
            if (minLeft == -1 && minRight == -1)
            {
                return depth + 1;
            }
            if (minLeft == -1)
            {
                return minRight;
            }
            if (minRight == -1)
            {
                return minLeft;
            }
        }
    };
    int main()
    {
        int arr[] = { 1, 2, 3, '#', '#', 4, '#','#', 5, 6 ,7};
        BinaryTree<int>bt(arr, sizeof(arr) / sizeof(arr[0]), '#');
        cout<<bt.ShortDepth();
        system("pause");
        return 0;
    
    }

巧妙地利用递归求解。把二叉树划分成为左子树和右子树，求解最短路径就是求解左子树里的最短路径和右子树里的最短路径，两者再做比较返回较小值。