美文网首页
Given a binary tree, find its mi

Given a binary tree, find its mi

作者: yueyue_projects | 来源:发表于2017-04-24 11:34 被阅读28次
    • 层次遍历法
    public class MinimumDepthOfBinaryTree {
        static boolean isLeaf(TreeNode root){
            if(root.left == null && root.right == null){
                return true;
            }
            return false;
        }   
        public static int run(TreeNode root) {  
            if(root != null){
                TreeNode temRoot;
                int count = 0;
                Queue<TreeNode> queue = new LinkedList<>(); 
                queue.add(root);
                root.val = 1;
                while(queue.size() != 0){
                    temRoot = queue.poll();
                    int layer = temRoot.val;
                    if(isLeaf(temRoot)){
                        return layer;
                    }
                    if(temRoot.left != null){
                        queue.add(temRoot.left);
                        temRoot.left.val = temRoot.val + 1;
                    }
                    if(temRoot.right != null){
                        queue.add(temRoot.right);
                        temRoot.right.val = temRoot.val + 1;
                    }
                }
            }
          return 0;
        }
        private static void build(TreeNode root) {
            // TODO Auto-generated method stub
            setLeft(root);
            setRight(root);
            setLeft(root.left);
            setLeft(root.right);
        }
        public static void setLeft(TreeNode root){
            root.left = new TreeNode(0);
        }
        public static void setRight(TreeNode root){
            root.right = new TreeNode(0);
        }
        //运用层次遍历计算
        public static void main(String[] args) {
            TreeNode treeNode = new TreeNode(0);
            build(treeNode);
            System.out.println(run(treeNode));;
        }
    
    • 用层次遍历方法很简单,但是用深度遍历法则需要好好思考思考,递归就是整体考虑,就把run当做了求最小值的方法
    class Solution {
    public:
        int run(TreeNode *root) 
        {
            if(root == nullptr) return 0;
            if(root->left == nullptr) // 若左子树为空,则返回右子树的最小深度+1
            {
                return run(root->right)+1;
            }
            if(root->right == nullptr) // 若右子树为空,则返回左子树的最小深度+1
            {
                return run(root->left)+1;
            }
            // 左右子树都不为空时,取较小值
            int leftDepth = run(root->left);
            int rightDepth = run(root->right);
            return (leftDepth<rightDepth)?(leftDepth+1):(rightDepth+1);
        }
    };
    

    相关文章

      网友评论

          本文标题:Given a binary tree, find its mi

          本文链接:https://www.haomeiwen.com/subject/nrauzttx.html